It really depends of the kind of pictures you want to take. Look at "What are the uses of Neutral Density (ND) filters?" for information about potential ND filter uses. You can also take a look at "What are neutral density filters and how do I use them to create long exposures in daylight?" to know more about those filters.

A direct way to know the ND filter you need would be to take a correctly exposed picture of the scene you want to capture (shutter speed "A") and then estimate the shutter speed you would like to use (shutter speed "B"). Now compute the ratio B/A and it will give you the f-stop reduction needed. If A = 1/50 sec and B = 10 sec, B/A gives 500 : you need a ND512 ND filter (9-stop reduction, because 2^9 = 512).

In my case, the first ND filter I bought was a "ND1000" because I wanted to take exposure of a few seconds in broad daylight. My estimate of a regular shutter speed was 1/250, so it becomes about 4 sec with a ND1000. Of course you can moderate it using different aperture and/or ISO.

Anyway, a rough estimate of the factor by which you want to multiply your shutter speed should be enough. You can also google pictures taken in Hawaii with ND filter.

ND filters ratings can be tricky. Take a look at Wikipedia (https://en.wikipedia.org/wiki/Neutral_density_filter#ND_filter_ratings) to understand the different ones.

As a side note, I would like to add that a ND filter with a high f-stop rating might prevent you from using the AF (and you won't be seeing much in the viewfinder).

As you already pointed out, cheap variable ND filter are to be avoided.