The first aspect would be to use an API which will generate an address with minimal input such as the users house name/door number. This helps with formatting issues as you generate the address as it should be and do not put that responsibility on the user.
The second aspect to this, is to add a manual set of fields in which the user types their address in themselves. Using form validation you can assess the information typed into each field and make sure it is in an appropriate format (I am in the camp that believe you should format trivial things yourself such as capitalisation of a postcode/postcode spacing, so try not to be really pedantic with your formatting if it can be avoided).
A permanently visible example of how to format a guide on what to input into each field. The font is grey and small to ensure that the form does not look cluttered. The text should also be concise.
Tooltips are useful if you need to add more detail into information about the form field. Remember to take into account mobile devices as they cannot hover over, so add in a fallback method.
These hints only appear when a field has keyboard focus. You instantly validate each form when the user has finished typing. This is a really nice way to go about it, as you give the user positive feedback after each field so they understand what they have typed is correct. Twitter use this to sign up for their service.
These are all appropriate for use but bare in mind the detail of the help you provide for each field. More complex descriptions would be better suited to a tooltip, whereas a shorter more concise description would be good with inline or dynamic.
Source for all of the above images and ideas