Santiago Guesthouse Naha is my favorite cheap hostel in Okinawa. Friendly faces, great staff, and dead cheap beds all year-'round.