Yes, Addresses uses the native systemwide address book programming interfaces, these are compatible with both iTunes and iCloud.
Note that there are compatibility issues between using iCloud and iTunes syncing. Essentially, if you use an iPhone without iCloud support, do not enable iCloud support on your Mac as the syncing is done between the local address book (which is separate from the iCloud version) and the phone. Worst case you get duplicated contacts in the list. Note that this behavior is identical to the OS X address book application.
This can be done in the Address Book application that came with Lion. Start it up and open the preferences. In the preferences window, select the general tab and then select the account next to the Default Account popup.
This was a problem for users who had disabled automatic window restore in the system preferences. The problem was addressed in Addresses v1.1.1. Please update the program using the Mac App Store.