Papyrus is only available to certain 6 Soul Traits. At the start of the game, you can check the Relationships tab in the Journal. If you see "He might be interested in you" then you have a Soul Trait he'd like. From that point on, you just have to choose the <3 options when available in Snowdin.
Also: You will need to agree to deliver Cinnamon's letter in Snowdin. She acts as an excellent wingman. :)