They're very common in hostels, particular backpacker hostels, but that fits with having limited luggage. I've seen them once or twice in the cheapest hotels.

The main railway station in a European town sometimes has luggage storage. In Germany that's usually lockers, in countries with more history of terrorism (like the UK) it's a room with a metal detector and an attendant.