I read online that I can take taxis, trains, airplanes, but is this even true? And how do I access them? Do they go to waypoints or only between cities?
Once you've unlocked San Fierro, you can catch trains from the train stations and airplanes from the airports. You can skip through the plane journey, so that definitely counts as fast travel, but I don't remember if you can skip through train rides or not.
If you haven't unlocked Las Venturas, the portion of track going there will be blocked off, and you won't be able to select it as a destination at the airport.
You can't fast travel with taxis.
Of course, you can also steal planes and trains; they can be faster than driving to your location.
The fastest way to go any significant distance in San Andreas is by plane, particularly jet airplanes. There's usually a private jet (a Shamal) parked on the runway at Los Santos airport that you can steal - the security gate at the airport won't let you in until you are a qualified pilot, but if you park a car in front of the security booth, clamber on to the car and then clamber from the car to the top of the security booth, you can then jump inside the airport.
Once access to San Fierro has opened up, you should be able to steal a helicopter from San Fierro airport.
A relatively quick way to travel within Los Santos is to use the storm drain network (particularly on a bike) - this enables relatively direct access to large parts of the city, without having to negotiate traffic / other gangs.
I haven't played for a long time, so my memory is a bit sketchy. I remember that if you fail and have to repeat a mission, you can see a way point to the nearest taxi, which you can hop on to get to the mission area.
I don't think this was San Andreas. Although if you fail a mission half-way through and restart it, I believe it gives you the option to 'Trip Skip' certain driving sections so you don't have to (re)drive halfway across the map. Could this be what you're remembering?– Robotnik ♦Jul 3, 2015 at 3:44
Use a Jetpack for faster travel between cities/mountains.
You can spawn one with the code
Jetpacks are good for jumping around inside cities, but if you want any form of distance (between cities) they can be fairly slow compared to other available options :)– Robotnik ♦Dec 11, 2015 at 4:28
I can bet anyone that the fastest of all to travel in GTA San Andreas is to apply the cheat "CHITTYCHITTYBANGBANG"(cars flying) and then then just steal a car and go on flying with the same control as of a plane.
*it is a bit tricky to control the car on its max speed as it is way too high, after you use it around 3-4 times you can get used to it