A cyanotype can be printed on almost any paper, cloth, or even tile. I used 100% cotton water-color paper from an art paper store. It was not fancy (about 2 euro for a huge sheet), nor thick (~170 lbs?). Some people are more careful about paper selection. For other's views, check out the Alternative Photography forum here
Brush, spray, or soak the sensitizer into the paper.
Leave the paper to dry, or speed it up with a hairdryer set to low.