Select your 'theme' from the theme menu - on that theme editor page you can select the check box "Allow Gifting:" which will add a gift message field in checkout.

You can also confirm the gift message in confirmation emails etc using the gift merge: ##GIFTMESSAGE##

With regards to an extra fee for wrapping - one suggestion is to create a 'gift wrapping' product and use the 'may we suggest' feature - when the product is added to the cart, the customer is then presented with the opportunity to add gift wrapping and/or other items.

Cheers