Our plan was to go to Kerala from here. If we had had a little more time, we would have gone to Kanyakumari, but we had a tight schedule and headed right to Alleppey, Kerala. The best option is to take to MS Guruvayur express train which departs at 15:00 and arrives in Alleppey around 2 in the evening. The distance is about 450kms. That means that you have to arrange your pickup in Alleppey since the railway station is 4km from the city and there aren't any taxis or rickshaws at the Alleppey railway station that late in the evening. The train makes a U-turn because there's a high mountain range called Western Ghats between the states of Tamil Nadu (Madurai) and Kerala (Alleppey) Therefore, first we traveled to the southernmost part of India (Nagercoil, 20kms from the famous Kanyakumari) and then started to go northwards on the seashore through Trivandrum and Kollam. Again, 2AC class (the best available) on the train cost about 1500.- Rs. for 2 persons. It was quite comfortable after the train trip from Bangalore to Madurai because the compartments on this route weren't that much crowded and we were placed together in the same place, one of us had a lower berth and the other was an upper berth right above the lower berth. It was ALMOST comfortable. Though I had to watch the stations again to be able to get out at the right station. The train stops at Alleppey only for a few minutes.
We traveled to Madurai from Bangalore. It is cc. 450 kms. Though Air Deccan had a reasonably priced but irregular flight between the two cities, I still decided to take the train. The overnight train journey lasts for about 11 hours and costs (the best available class, 2AC) 800.- Rs/person. Make your reservation well ahead since the train we took (Tuticorin express) is very crowded and you are likely to get only upper berths in the compartment if you run out of time. It is also possible that you cannot travel right beside your couple. You are likely to get a berth in the same compartment but far away from each other.
Note that if both of you have upper berth, you can have problems with storing your luggage because you have to place it on the upper berth which is a short and narrow place (can you call it a bed? it is more like a shelf) to sleep on and even more uncomfortable if you have to make place for your luggage.
If you have to take more overnight trains during your journey, it is a good possibility to get used to the conditions. It is safe and reliable but way too crowded and uncomfortable compared to western standards. But hey, it is India, you have to try it and get used to it.
And you can spare one day of accommodation by sleeping on the train (if you can really sleep, it is not impossible but one of you has to watch the time and the places the train goes through because names of the stations are not announced, so it is your responsibility to be awake and get out of the train when you reach your destination).
By Air : Madurai has its own airport, located 12 km from the city center. There are daily flights to Chennai and twice a day flights to Mumbai.
By Rail : Regular trains connect Madurai to Coimbatore, Chennai, Rameswaram, Kanyakumari and other towns of South India. The Madurai Railway Station is within the city center.
By Road : Madurai is very well connected by a network of roads and road transport to all major towns of Tamil Nadu and surrounding areas.
The best way to get around Madurai city is either auto rickshaw or cycle rickshaw. Cycle rickshaw is a bit cheaper than auto since it doesn't consume petrol - but takes lot of driver's physical effort. Cycle rickshaw is good only for short distance.
Try barganing with the drivers - auto drivers in Madurai are most dificult people to bargain with, but otherwise they might come up with a high fare. Agree on fare before getting on to the rickshaw.