Well, when you depart your cruise ship there should still be a welcome center place to your right. Go through or around that building and various taxi stands will be present. When we've taken taxis from here in the past they've always been pretty good, and we've actually learned a lot from having conversations about the island from the drivers. It is a fixed cost to Orient Beach or anywhere else, but the amount is typically lowered if you share a taxi with others. One time we paid as little as $7 each when we shared a taxi van with two other couples. Otherwise, it should be about $25 USD or so. You may wish to ask the taxi driver to return to take you back at a specific time to ensure you don't miss your departure time from the port, but in the past we never hard a problem finding a taxi around Orient Beach. Hope this helps.
.
