Here are some tips about planning a trip to Trikora Beach on Bintan Island from Singapore. It's really close from Singapore, you can really go there only for one night, even if it should be nicer to stay there 2 or 3 nights. The place you definitly have to go there for accomodation is the Shady Shack, a 5-hut "resort" lost along the beach. I wrote resort ironically because it's all the contrary : very simple wood huts, one matress on the floor, common meal for everybody and sharing of common life. If you're looking for the confort of an resort and the easiness of being among all tourists, you'd better go to the northern shore resorts and stop reading this post :). But if you're looking for a peaceful place, without too many tourists (well, depending on who they are, 10 tourists can already be too much but ...), where you can meet friendly local people and all this for little money, Shady Shack is the place to go and my pieces of advice should help you !
If you're reading this post, you probably know where Indonesia lies and where Bintan Island is, but for those who need to remind, the following can be usefull :


Bintan is just in the red square above ... quite small isn't it ?
The trip should probably follow the red line on next picture :
- Ferry from Singapore to Tanjung Pinang
- Taxi from there to Shady Shack, and you're gone.

It's quite fast : 1hour 1/2 for ferry and 1 hour of taxi. Let's go into details ...
Ferry
You will have to take the ferry at Tanah Merah Ferry Terminal (not far from Changi airport). Quite long to go there from NUS. You could take the MRT to Tanah Merah MRT and then take the 35 bus (right side when you exit the station, should be usefull when you're in a hurry :).
Three companies operate the line, one of these is Penguin. There are a few departures everyday, timetables are online. We took the first one in the morning, around 9.30.
Price both ways is around 55 s$. You will pay around 50 $ when collecting your first ticket in Singapore, then 2 $ (10k IDR) when collecting your return ticket in Tanjung Pinang and then 13k IDR again to enter the harbour.
Ferry takes around 1hour an half.
Visa
When arriving to the harbour, you will have to get a visa. The on-arrival visa system works for most western countries, you should check if it applies for you. Price of the visa is 10 US$ for a 7-days-long one (25 $ for 30 days). We paid in US dollars, there was no problem, you will even avoid the queue of local people :).
Taxi (Tanjung Pinang to Trikora Beach)
If you've booked at Lobo's shady Shack, it's likely that Natalys will be here to pick you up. He will wait outside the harbour with a sign showing your name ... Otherwise you would probably find one of these vans to go there. Ride is around one hour. Price is normally 25s$ for the taxi (150k IDR). Their driving is quite scary, but you're quickly used to it :).
[edit: other people only paid 12s$, seems possible to have cheaper fares. Well, if you really want to spare this, feel free to say no to Natalys, but to my mind, it's not really worth: you will have to find someone else (not hard i think) and above all, Natalys is a friend of Lobo, you will already arrive there with Lobo having a bad prejudice, so if your purpose is to have friendly time with them, it's not very good ...]
Nothing much to do in Tanjung Pinang I think, spent one afternoon there, well it's a typical city but once you have eaten something, you can shop for a while and have a drink, nothing really interesting ... Of course it's not for sure, so maybe you could try and discover things we've missed :). And it is quite nice to be among Indonesian people without any other tourists, you really have the feeling of living a typical experience. We were there for carnaval, it was very crowded. You can look at the photos in this french post, image is kind of universal language :).
Accomodation : Lobo's Shady Shack
As already told, this little guesthouse counts only 5 huts. Think it is a good thing to book before, because there's not much much place to go around ... You can find Lobo's number on the website. To have a better idea of what it looks like, you can try to have a look at my pictures. Post is in french but you will probably understand, it will be enough to make you dreaming of going there :)
Price for the night is around 20s$ per hut, including breakfast. Food is quite inexpensive as always... Don't really know the price, but including some beers, water and coconuts, i paid 44 s$ for 2 nights sharing my room. We booked by SMS and then calling him, but SMS should be enough I think if you give him name, date and number of hut.
There is hardly anything around there but sea, sand and coconuts. You'd better grab some books before going :) (well, you can also play chess with the old man or just enjoying the sea, it's not that much a problem :). If you need something (let's say some beers for example ...) you just have to tell Lobo who is going to the village with his motorcycle and brings this back. Beers to finish about this, are quite cheaper than in Singapore, around 24 s$ for a 24-pack (it's roughly the price for a 6-pack in town) and could help you to make local people friendly I think.
Nothing much more to say about the place ... People were very friendly, some guys came and played guitar, sang local songs, it was really nice. Lobo usually lights a fire on the beach at night, quite nice too. You have to go there and make your own experience, but to my mind it is really worthy from Singapore for a long week-end and even a normal one (2 days).
Hope this post could help, please do not hesitate to comment if something is wrong or just to add something !