Both of the above are right. Just to clear it up in case you are confused you ALWAYS have to have the free version installed on your device. Then you have a paid license. You can get the license by downloading it from the market or by going to the dev's website and paying for a license file. Then when you load the application (the free app) it will tell you it is the licensed full version.
As a side note, if you have downloaded the free version and license and it still says it isn't licensed you can clear data and then try reloading the free app or uninstall the app and re-install it and it will work fine.