There are lots of locally produced maps. The University of Hawai'i Press ones are the best and cheapest. Look for the blue and green printing on a white cover.
Don't miss the farmers markets and thrift stores. The latter are particularly good places to find an aloha shirt. Don't buy too much local fruit, though: you won't be able to bring it back to the mainland.
I particularly enjoyed our two nights at Hotel Manago in Captain Cook on the Big Island. It's a trip back in time to 1938, with only the barest of concessions to the modern age: no phones or TV in the rather spartan rooms, but a pretty Japanese garden, and the beds were firm and new, easily the most comfortable I've had anyplace that cost less than $50 a night.