Kuala Lumpur is the capital of Malaysia.
There is a big toll gate south of the city which is an excellent hitchhiking place, but not too easy to reach. First, take the LRT to Sungai Besi. From there you have to walk south along the main road. You have to cross the rail tracks on your right, either by jumping the fences, which is illegal and somewhat dangerous (it's a high speed train line) or you can use the bridge which is quite a walk. [in which direction?] Walk further south, you will see a McDonalds on your right and then a little neighbourhood. The south end of the neighbourhood is right next to the toll gate. The motorway is elevated here, but there is a little hill with a little footpath that leads to a hole in the fence exactly at the parking place behind the toll gate from where you can start to hitch. It'll take you about 45 minutes to walk from the LRT station. There is probably a bus that stops a little closer to the toll gate. It's very possible to get a direct lift to Singapore from this place.
If you don't fancy a long walk or dicing with death/police by crossing rail tracks - this is a somewhat easier option. Take the LTR in the direction of Seremban and alight at Serdang. Once you exit the station turn left, and cross the busy carriageway over the footbridge. From here walk two minutes in the direction of traffic to the flyover. It might seem a little nervy at first, but the traffic is slowing up the hill and into the bend, and there's more than enough room just before the apex for vehicles to pull in. You're not quite on the right road yet for Singapore - but a sign saying highway E2 will get you a ride in no time - most probably dropped at the next toll station south.
Another save option and only a five minute walk is to take the LTR (metro/train) to the same stop as mentioned above: Serdang. Exit the train station through the gates. Than take the walking bridge that leads you to the other side of the rails, to a playground on the opposite of the trainstation. You can already see the highway E2 from the bridge, walk straight in the direction of the highway until you can't go further. Walk about 100 meters to the right and you'll find a small stairs where you can enter a rest station (R&R Serdang) at the E2 highway. From there you should easily get a ride in the direction of Melaka. It's also the right highway to Singapore. There are a couple of restaurants and toilets.
North towards Thailand
The first one is a Shell gas station right behind the toll gate (it is at the Plaza tol Jalan Duta). In order to get there, you can take the KTM commuter train and get off at the Segambut station. From there, walk about 1.5km south on the highway.
The other place you can consider is a toll gate near the KTM station Sungai Buloh. Get off the KTM commuter train at Sungai Buloh, walk down the stairs and you will come to a motorway. Turn and walk left then walk across the overpass to the other side of the motorway. If you are facing the train station you just came from, then walk right along the side of motorway. Initially you will walk under a motorway bridge, keep walking straight along the side of the motorway. It will get quite narrow but walk on the inside of the barrier. To your right you will see a flood water and then the toll booth you are trying to get to. Continue walking straight, you will come to a plant nursery on the side of the road. Go through the gates but keep walking in the same direction as before. You will come to a small pipe opening with water. You can easily climb and jump the fence to get over then continue walking. You will come to an over bridge where you can walk along to the right which will put you on the road to the toll gate. Walk along the side of road towards the toll gate, walk past it, run across to the other side and be sure to stand on the shoulder of the lane heading straight through, which is the "labuan besar utara selatan" (big road from north/south)
Take the KTM train heading north and get off at the last station called "Rawang". You'll arrive at this town "Rawang" that is not on the highway but you can reach very easily, just a short 5 minutes walk, another main road going north (toward: Tapah, Ipoh, Cameron Highlands, Penang, Thailand border, etc.). That is probably not the perfect way to head north if you are in a rush, because you'll have to deal with short and indirect lifts until you get to Tapah (about 100km north of Rawang), but it's not a bad option, hitchhiking on that road is very easy.
A very good option from the Rawang stop is to take the roughly 20 minute walk to the main North-South highway. Once you get off at the station, walk south along the main road (Jalan Rawang) and follow the off ramp on the right side of the road (traffic should be flowing in the opposite direction) up to Jalan Batu Arang. Follow this road, and take the right at the first lights onto Jalan Kuala Garing. Follow this road until you reach the second fork, and take a left (the road should be a relatively unused, beat-up path). You should see the highway ahead, and within 200 meters this road will take you through a narrow tunnel under the motorway. If it doesn't, you probably took a left at the wrong fork. After the tunnel, turn right and walk until you see the rest area...you will have to hop over the low barrier to get to the rest area. There, you will find a gas station, Starbucks, a hotel and other facilities...and most importantly, many cars heading North. Hitching a ride from there is very quick and easy.
East towards Kuantan and Kota Bharu
You need to E8 which takes you to Bentong and then either to Kota Bharu or Kuantan. To do this take the KTM to Batu Caves and start walking east along road 28, you could either keep on walking east along road 28 until you reach the McD and Petronas station 3km away or you can make a sign that says Petronas or petrol station and hitch along road 28. Once you get to the McD you will get a ride within 5 minutes
Sleeping on the streets, while not necessarily suggested, is entirely possible with no problems. Find a closed business or Monorel station and lay down for the night. This might not work in areas such as the Golden Triangle, but is viable in other areas. Simply be aware of the traffic. Choose a good area and you should be safe. Good places include near the river in Chinatown behind some buildings is a rather secluded area, the large area of parks (Deer Park, Hibiscus Park, Orchid Park - also good for stashing your things) close to the National Mosque west of Chinatown for being close to downtown. Outside the gates of the Batu Caves looking at the highway, turn right. You are heading toward the Monorel station. Once you reach a T-intersection, to your right are a series of benches with cover perfect for sleeping if you are on your way out of the city.
Kuala Lumpur is a relatively small city and is perfectly walkable. Just make sure to not get lost.
Kuala Lumpur has a fairly decent public transportation system comprised of trains and buses. You can get from KL Sentral to any major area of the city. The trains run from around 5AM to midnight.
There is an entirely free system of buses known as GoKL (). These purple buses go to various malls and tourist attractions, but can successfully be used to traverse the majority of the city.
At KL Sentral there are many lockers available for use. There are two different kinds - the ones near the escalator toward the exit, close to the bathrooms and those on the way to the departure gate for the KL Ekspres to the airport near the escalator heading toward the mall. The lockers toward KL Ekspres are MYR 2 for 24 hours, including overnight, and MYR 2 for every hour over 24 hours. The lockers near the bathroom range in price from MYR 5 to 20 and do not allow for overnight storage.