Wikipedia actually has a section on this in their kotel article. This is the main source quoted. The bottom line in regards to disposal is that periodically the Kotel is cleaned out and the notes are burned, seemingly because burying them would be too monumental a task and 'traditionally' they have been burned.
In regards to the question of whether or not they are 'Shaimos' (sacred items that intrinsically require ritual disposal), I don't believe they are by the mere virtue of being in the Kotel. If, however, they contain a divine name or a pasuk or some other form of scripture, then they would be. In other words, a letter saying 'Please give me success' would probably not be shaimos, and could be disposed of like regular garbage. A letter saying 'God, please grant me success' would likely require a ritual disposal. For more on shaimos here are some guidelines from shaimos.org.