Despite its large size, most of Johor is covered with rubber and oil palm plantations, with few historical attractions or natural wonders. Most people just pass through on their way between Kuala Lumpur, Singapore and the islands of the East Coast.
Johor Bahru is on the Malaysian rail network and has an airport with good connections around Malaysia.
Flying in is pretty convenient, directly to the Johor Airport
By bus, from Singapore From SIN Changi Airport, take the TS1 Bus ( http://www.regentstar.travel/crossborder/ ) for SG $10 which will take you to Singapore Woodlands CIQ (immigration). Pass through immigration (which can be slow on Friday's due to weekly migrant workers), take the SBS 170/160 bus (follow the crowd), and pay $1 to board, which will take you to Malaysia Johor CIQ. After passing through immigration, hop back on the 170, which will take you to Larkin Bus Station in Johor Malaysia.
To get back to Singapore from Johor, buy a ticket for RM 4 for the Singaore Johor Express (SJE) from the Larkin Bus station, which will take you all the way through Malaysia + Singapore immigration, and drop you at Queen Street bus station in downtown Singaore next to Bugis MRT.
Generally, if you're at any of the major bus stations, and say the place you want to go, eg. "Batu Pahat" they'll direct you the right way. The bus station may look super chaotic with 40+ private bus lines, but the people there are helpful. Busses run approx every hour (sometimes every 30 mins). Look at the front of the bus for the sign, and when boarding the bus, confirm w/ the driver (just say "Batu Pahat"). Note that when you're at immigration, the bus will not wait for you. Just find the next bus of the same company/destination that comes.
Virtually all transport in Johor radiates out from Johor Bahru.
Legoland has recently opened, and is the first of its kind in Asia, and only the sixth in the world.
Legoland is located at Gelang Patah, Nusajaya.
Johor's culinary specialities include mee rebus, spicy noodles in sweet potato soup, and Johor laksa, an offbeat version of the ubiquitous noodle dish: in Johor's version, the usual rice noodles are replaced with yellow egg noodles (not spaghetti) and topped with a thick paste of fish, onion, peanuts, chili peppers and spices.
Mee Rebus Stulang, Kacang Pol Haji, Sayur kangkung Cincin Mas and others will surely bring up the mood plus with the nicely done ABC special, cendol and other varieties of hot drink to choose from.
The crime rates are increasing, especially in state-capital Johor Bahru, the region along with Malaysia's main cities(eg: KL, Penang, etc) is getting more dangerous, with even random stabbing and snatch theft(even from your bike & car) on the rise. Tourist in general make easier targets, as they are easily distracted by the new surroundings and more of a hassle for them to report the crime (due to language and time spent in one location)
Take care of your personal belongings whilst strolling along the streets, particularly when alone. Do not dress inappropriately (primarily out of respect for local customs and cultures) and do not show expensive jewellery or count large amounts of money in public places. Take the same common-sense precautions you would elsewhere.