I may have not properly read the paper that said "This is not a visa, you should apply for a visa using this paper"...

You probably had a CoE (Certificate of Eligibility to Reside in Japan, 在留資格認定証明書). This piece of paper needs to be taken to your local embassy or consulate and be converted to a visa there, which then gets stamped on your passport.

But Japan is working quite differently from other countries here, so you're probably not the first person to be confused, although I don't think any country issues a long-term visa that is not stamped on your passport.