Generally I use regular RC paper (trimmed to size where required) and stick address labels on the back.
I use the address labels that are designed to go through a computer printer (Avery brand or a competitor). One label includes the addressing information, while one or two other labels includes any other information I might decide to include. I prepare my labels on the computer, but for those who prefer to hand write them, you can always stick the labels on blank, and then write on them.
I have seen postcards on fibre paper, but they are a bit less durable.
I think I have an extra card or two from the most recent exchange - pm your address to me and I'll invest 28 cents in a US stamp and send you one .
EDIT: as you are in the US, you will want to pay close attention to the USPS specifications for postcard size, in order to take advantage of their very favourable pricing. IIRC, a 4x5 card is too small, and a 5x7 card is too big. 4x6 is just right. I certainly have received cards that consist of a contact print from a 4x5 negative on a 4x6 card.