There was a fairly publicized incident in my city about a decade ago when an upscale hotel refused to allow an under-21 military couple to check in for their honeymoon. They had to do damage control by isuing a public apology and offering a free stay.

While some hotels, particularly in resort areas, may still have such a policy, I think it's relatively rare. The safest thing would be to call in advance and confirm. I also second the youth hostel suggestion, many of them these days have private rooms as well.

Edit: under 21, not 18