From Medan there is a local bus (no air-con) about every hour for 18,000 rupiah if you pay on the bus. The journey takes 4-6 hours, depending on the traffic condition.
Take a ferry boat to cross over to Samosa island.
Water Scooters (150,000Rp per half hour, with a guide on-board)
Speed boat rides
Self paddle "kiddle ride" boats (40,000Rp per hour)
Charlie's Guesthouse - good place, meaning cheap and central. Overlooks the market (a bit noisy especially on Saturday) and is very close to the ferry station. Rooms are about 30,000 rupiah, pretty clean and with shower (2006).
Niagara Hotel and Resort - One of the better hotel you can get there, though only 2 to 3 stars. Can be crowded with families and Indonesians during peak period (weekends and public holidays) http://www.niagaralaketoba.com/