What transportation options are there available (buses, shared taxi, taxi, or else)?
Note that I do NOT have my own car.
As far as I know there are two possible ways to get to Lake Toba from Medan.
The easiest way to do this journey is to travel on a tourist minibus. It is a bit more expensive than the public transport option but it also gets you faster to your destination and you do not have to worry about transfering buses, finding the right one, waiting for it to leave, etc. You will travel by road from Medan to Parapat, you catch the bus from the Pinang Baris bus station in Medan. The price should be around 90,000 Rp. From Parapat you will be dropped off at the port, from where you will take a ferry to Palau Samosir, the island in the middle of the lake. The ferry costs 15'000 Rp. We were actually travelling from Bukit Lawang to Samosir island. We took the tourist bus for 230.000 Rps. The bus left from Bukit Lawang at 8.30 am and arrived at Medan at around 11.00 am. After a short break we continued on the road, reaching Berastagi at 1.30pm. After another break we then headed to Parapat, another 3 hr drive, so we arrived there at 5pm. Then we had to wait for the ferry. The ferry ticket was included in the total price we paid. To go from Bukit Lawang to Berastagi, same journey costs 170,000 Rps.
There is another way to reach Danau Toba by using public transport. We did not go for this option, so I do not know the prices, but it is definitely cheaper than the above option. It is also a bit more complicated to reach the destination, timewise. You can take a public bus from Medan to Berastagi, from there catch an opelet to Kabanjahe, then transfer to a bus to Pematangsiantar and then to another bus heading to Parapat.
On a small note, a tourist bus from Medan bus terminal to Parapat should cost about 65,000 Rp. A private taxi (fits 6 passengers) from Medan airport to Parapat should cost about 120,000 Rp.
Further info: SAMPRI buses are the local public buses that seem to be the most 'official' ones. The price is fixed and told straight-forward, no need for bargaining. At some point shortly after starting the journey (on our way to Banyak islands) the bus drivr stops at a booth where you purchase your ticket and get a receipt with price and stamp.
In addition to taking a bus/minibus, you can also fly to Samosir island by taking a flight to the relatively new Sibisa airport. You will land a few kilometers from the ferry to the island.