SELECT * /* Consider specifying columns */
FROM eanprod.activepropertylist
(
    SELECT *  /* Consider specifying columns */
    FROM eanprod.activepropertylist
    WHERE StateProvince IN("NW","WA","SA","NT","VC")
)
ORDER BY RAND() 
LIMIT 4

EDIT: Just realized you said one in each state, can this not be done in PHP for some reason?

IMHO it's faster to do the random select in PHP

Here ya go

/* Consider specifying columns in selects */
SELECT * FROM(
    SELECT *
    FROM eanprod.activepropertylist
    WHERE StateProvince IN("NW","WA","SA","NT","VC")
    ORDER BY RAND()
) AS shuffled
GROUP BY StateProvince;

Thanks That words

But I would like to get 4 hotels from each state (36 total) in this query though.

It only get 1 hotel from each of the states