This all depends on 2 main factors:
- The resolution (pixels/inch) of your document
- The original size of your brushes
If you make a new document of size A4 (21cm wide x 29.7cm high) at a resolution of 300 px/in (the usual setting for printing), your document's pixel dimensions will be 2480 px wide x 3508 px high. In Photoshop CS3, the maximum size of a brush is 2500 px (along its longest dimension).
This means that if you have some brushes close to the maximum size permissible in PS, you should get reasonable results working with them on a document of that size.
If your brushes are smaller, you have two options:
- Firstly, you could increase the size of the brushes from the default. Depending on the brushes you are using and the way you're employing them, relatively small increases in size shouldn't be too much of a problem, but if you try increasing a 200 px brush to 2000 px don't be surprised if the results are horrible.
- The other thing you could try would be to reduce the resolution of your document. Although 300 px/in is the default setting for printing, you may find that you can achieve acceptable results with a smaller resolution. If you reduce your A4 document to 200 px/in, for example, the printing size (21cm x 29.7cm) won't change but your document's pixel dimensions will now be 1654 px wide x 2339 px high. This means that brushes with smaller default sizes will appear larger. Of course, if you reduce your document's resolution too much, you will get unacceptable results when printing out, but it's really a case of trial-and-error.
The whole concept of Pixel Dimensions/Document Size/Resolution can be very confusing, but I hope this has helped.
PS: There are some high-resolution brushes available that are especially designed for documents destined for printing. You can find some good links here:
High Resolution Photoshop Brushes - Free Hi Res Photoshop Brushes | PhotoshopSupport.com