Love hotels certainly are some of the most fascinating things of Japan, especially the history. Read Japanese Love Hotels: A Cultural History if you are want to know the fine details and get a good amount of recommendations as well.
They can be nearly found anywhere in Japan, in Tokyo Shibuya and Ikebukuro are the most famous areas and you can really miss finding them. Prices start at about 5,000yen per night, which is really good. However you do have to pay more if you want something more fancy or say a themed room. I would recommend checking in around 9 or so in the evening, this way you are before most other couples and can select your own room.