Large enough to fit in the map plausibly.
For your specific task, it really depends on what the sign's supposed to do. Are we talking the billboards you see along major roads in urban areas? Signs on the windows of businesses? Street signs telling you the road name? Either way, map out how large you want the sign in question to be with some other stock texture, like GFZROCK or something, and once you get a feel for that, make the relevant texture. Simple as.
Bear in mind that textures larger than 255 pixels tall need multiple patches to create (ie, it has to be broken up into two parts for the PATCHES lump and pieced together in the TEXTUREx lump), and that the width must be a power of 2 (2, 4, 8, 16, 32, 64, 128, 256 etc).