You do not need to be online to generate addresses. The whole process takes place without an internet connection, and the blockchain know your address when you sent or received from that address.

offtopic:
I want to know how to check that those sites is generating addresses randomly enough? I have read about bitcoinpaperwallet[Dot]com back doors.