my first recommendation would be to try to get a better flight out of Ft. Lauderdale if you can. Ft.Lauderdale is so much easier and nicer than Miami, and can be cheaper also. If thats not an option then i would look into a post cruise tour thru the cruise line, or book a day stay room at a local hotel
we just got back yesterday late flight. didn't realize could no tcheck baggage until 4 hours prior to flight. place in fort lauderdale that will hold bags for $6 per bag and we took a taxi around. found out later southwest airlines has a program for $10 per bag and they print out your boarding passes -- which would be the way i would go next time because a real pain to check in on the ship.. have to pay for the internet.... we also were gonna do the everglades tour but left the ship at 8:30 still to early after the tour to sit at the airport .... good luck......
I don't have a suggestion about where to store baggage but one of the best deals that I have seen is taking the water taxi.
If I remember it was about 12 bucks for the day with on and off privileges. You get a tour of the inter coast water way in Lauderdale, can get off at many interestings spots.