Lets start from the beginning. What camera are you using? is it set to best quality? if its yes to the last and your using a decent camera then it should print an A4 size ok.
Next what are you actually doing to the pics? are you editing the pic and saving or editing and closing then reopening and doing more work later? the more times you save and close a jpeg the more it affects quality, try and do all your editing in one go, or if not save a PSD for the edits and reopen that one and then just convert to jpeg at the end.
Now the last bit, when you finish editing are you resizing for the A4? if not how are you getting it to the right size? if you are resizing how are you doing it?
Can you tell us the file size on an original image and the file size on one after you have edited it?
Theres so many variables we need more info to work out exactly what your doing.
Wayne