By air
Singapore is one of the largest and most important transportation hubs in South-East Asia, which means that just about any major airline will fly you there. You can find a list of airlines flying to Singapore at Singapore Changi International Airport website. If you have an opportunity to fly Singapore Airlines, grab it; they offer an exceptional standard of service and in-flight entertainment. In addition, you will never be hungry on Singapore Airlines inter-continental flight, because you can always ask for extra snacks between meals.
There is a shuttle service from Kuala Lumpur to Singapore and vice-versa, operated in co-operation between Singapore Airlines and Malaysia Airlines. Discounted tickets are sold on a first-come, first-served basis. Due to a large number of flights between the two cities, you will most probably never have to wait more than a couple of hours.
SilkAir - the regional wing of Singapore Airlines is worth checking out if you plan to continue your journey to exotic locations around South-East Asia.
Budget airlines have made their way to Singapore too. Currently there are three no-frills carriers operating flights to/from Singapore: AirAsia, Jetstar Asia/ValuAir and Tiger Airways. All of them offer on-line reservations.
By bus
You can easily get to Singapore by a long distance bus from any major Malaysian city. Transnasional is the biggest Malaysian bus company boasting the most comprehensive network, adequate buses and good drivers. Their business class coaches are extremely comfortable. Don't forget to bring a warm sweater if you plan to take an over-night bus - air-con is always set to full blow. Most long distance buses from Malaysia will drop you off at Lavender Street Station. From there, you can take a cab or a bus to the city or walk to Lavender MRT station - it's about 700 metres away.
Budget airlines flying beeween Singapore and Kuala Lumpur caused hard times to bus companies, some of which now offer exceptional comfort, service and prices. Also, keep in mind that by travelling between Singapore and Kuala Lumpur by bus you won't need to go to the airport well before the flight, check-in, wait to board, wait for your luggage at the destination etc. So bus travel between the two cities could sometimes be a good alternative to flying.
If you are in Johor Bahru you can travel to Singapore by a local, non air-con bus No. 170. Keep your ticket handy as you will need to get off the bus at the Malaysian border crossing checkpoint, clear customs, take another bus, get off at the Singaporean border crossing checkpoint, clear customs and then take another bus. Your ticket is valid throughout the journey, whichever No. 170 bus you take. Do not try to do it during rush hours - unless you like to be squeezed by unimaginable crowds of Malaysian workers flocking into Singapore in the morning and back to Malaysia in the evening.
If you are masochistic enough to take a bus to Singapore straight from Thailand, you will most likely end your journey at Golden Mile Complex at Beach Road. It's a big, busy and confusing terminal. Lavender MRT station is walking distance away.
By train
Singapore is the southernmost point of Malaysian railway system. The land on which Singapore's train station and track is built actually belongs to Malaysia and is one of the everlasting disputes between the two countries. The good part of taking a train is that unlike when travelling by bus, you only need to get off and on the train at the Singaporean border crossing checkpoint at Woodlands. The checkpoint is considerably less chaotic than the one you need to pass through when travelling by bus. Malaysian customs officers will get on the train at Johor Bahru and perform their duties on board, so you don't need to get off the train to clear Malaysian customs.
You can take an express train to Singapore from places like Kuala Lumpur, Ipoh, Butterworth, Jerantut and Wakaf Baru. Check Malaysian Railways website for details.
By sea
Singapore has a number of sea connections with Malaysia and Indonesia. We have never used them, thus we are unable to provide any first-hand experience.