i found it easy to cruise (and travel in general) with our daughter when she was only 4-5 months old. it's great because they sleep a lot at that age. i don't know about your child, but mine was always happy to sleep in her carseat/carrier, so that made it easy to tote her around as well.
for us, the worst age was around 17-18 months, travelwise. at that age, she was very mobile, but didn't quite "get" everything that was going on. especially on a cruise - all she wanted to do was climb up and down the stairs!!!!!!! sigh.
she is 28 months old now, and is quite a traveler. and while she still enjoys climbing stairs (we dont' have any in the house, so i guess it's a novelty for her), she also enjoys other facets of a vacation. we just returned from a weekend at WDW and she enjoyed all the shows, plus the parade and fireworks. whew!