Oh, great question!
Technically speaking, as long as you design it properly (that is, entirely made of vectors) the size shouldn't matter.
However, to be safe, it would be a good idea to make it reasonably big - maybe 4000px wide.
The first step is to literally sketch some ideas with pencil on paper. Have you done so? If so, may I see?
Here's some related reading: http://www.damiensymonds.net/2012/01/creating-saving-and-using-watermark-ps.html
This is also relevant: http://www.damiensymonds.net/2010/05/making-pdfs-from-photoshop.html