This is small gift I made for my girlfriend for her birthday.
I got the idea from this link and decided to make my own one.

You don't need any special skills or tools for this as it is quite easy to make.

I found all my stuff at my local store for a total of 15$

Step 1: What You Need

Parts:
Bottle whit cap
Key
Piece of thin hard wire
Piece of paper
Decoration stones

Tools:
Knife or scissors
Glue

I got lucky and found a bottle whit a heart shape, but you can buy any shape you like or find. The bottle in not the important part of the gift, the key is. You have to bare in mind that your key needs to fit through the bottle's hole.

The bottle cap has to be made of plastic at the bottom, like mine, or a cork so you can pierce it.

Find a key you like. There are quite a few on eBay or in a local store. Look for key chains, or for jewelry like pendants. I got my on a key chain.

Step 2: Attaching the Key to the Bottle Cap

If you get the key from a key chain, like I did, just remove the key from the rest.
Leave a bit of the chain so the key hangs deeper in the bottle.
If you didn't get a bit of chain like I have, you can use a piece from an old pendant or a simple piece of thread will do.

Now take the piece of wire, bend it to a "U" form, put the chain through, and pierce the bottle cap in the middle.
If you don't have a piece of thin hard wire you can use a staple from a stapler or something similar.

Now you have a key in a bottle!

Step 3: Message in a Bottle

Now, you can do this by simply writing something by yourself.
For us who have horrible handwriting use the printer.
Best would be to write something you compose yourself, but you can look on the web if you don't have ideas.
I used Google and found me a few poems and mixed a bit of it whit a bit of my own and got a really nice short poem.
You can also just write a love line like "I love you" or "The key to my heart".

I also found a nice image and put it in the background of the poem. Used MS Word for all of it.
Pick a nice font that fit you (I was a bit limited because of my language letters) and center it. Put in the image and set text wrapping->behind text. Now Put the image behind the text. If the image (including empty space) is larger then the text you can turn picture border to show so you can easy cut the image lather. I also used recolor->washout (I use MS Office 2007 btw). It gave me the effect I wanted. Try some of them out to see which fits you best. Last I set color text to purple and was done.

Use a knife or scissors to cut the paper. Make sure it is not longer then your bottle. You can change this by changing the font in Word.
If you don't want a image you can leave it white or write/print on a color paper.

I printed a small heart image, cut it and glue it in a tube form. Roll up the paper whit the poem and put it through the little tube form paper. This way it is easy to read it and put it back in. Put it in the bottle and you have a nice Message in a bottle whit a key.

NOTE: message should say something about the theme "Key to my heart" or the key has no point being there.

Step 4: Additional Decoration

I found it nice to put something on the bottom of the bottle so I found some little decoration stones and put in just a bit.
You can put in anything you like. Flowers for example, but those don't last long.