When you go to profiles in the setup and create a new profile it will ask you to clone it from a particular profile that is already there. You can then pick a profile that has the required licence already. There will always be some tweaking of the profile. You can not clone a profile that has a different licence type and change this. (I've tried it myself)
I haven't tried it, but you could try to go to the salesforce IDE and edit the xml of the profile.
It has an entry
<userLicense>Salesforce Platform</userLicense>
Change this and see what happens (on a sandbox of course!)
EDIT: I've just tried it, but you can't change the licence type with the Force.com IDE.