I've been on some 16 cruises in the Caribbean, and have never, ever had a problem finding a taxi. They know when the ships come in and cruise ship passengers are a main source of income for the drivers. When you get off the ship, or arrive at the tender pier, there will be a whole line of taxis. The driver will almost always agree to pick you up at a specific time to return you to the ship and they are very reliabe. Even when I don't arrange this, it's been no problem finding a taxi. You're more likely to have to tell drivers that you don't need a ride than to worry about looking for one. If none are currently visible, ask a vendor or business if they will call you one. Vendors often have deals with drivers or cab companies and get some sort of commission for getting them fares.
As far as deciding what to do, a good guide book, such as Frommer's "Caribbean Cruises and Ports of Call", will give you a lot of options for each port, along with contact information and a web address, if applicable, for various tour vendors. You can use the book to get an idea of what to do, then contact the various businesses directly to make reservations. Make sure you know their cancellation policy, just in case the ship does not make the port call that day. Most will refund your money in this case.
There are also a lot of things you can do on your own for which you need no reservations, such as beach days or sightseeing. You can even strike a deal with a cab driver to give you an island tour. In this case, make sure you agree on the price up front.
Good luck!