Being able to match the beats correctly and bring two songs that are different tempo, together in one mix is a fundamental skill ANY DJ must learn. It requires mind-numbing hours of practice to get it right. Some people learn it straight away, whereas others take weeks, months even years!
When I started DJing it took me 5 months of solid practice to even start to get it right, now after a year and 5 months I have finally started to get my mixing, so that I get my mixes decent every time.
A good way to start to learn is to listen to other DJ's, Pro's if you can by either listening to them on the radio, a CD or at a club. By doing this you can learn different ways to mix and also learn how they do their sets, more on sets later.

When you first start to mix you will probably be totally crap, as are most people, unless they have had practice on decks before that is. One reason you can't mix very well might be because you can't hear the beats very well.
Listen and hear the beats when mixing, because if you can't hear the beats how are you going to mix!

Firstly you will need to know what beats are, in order to do a good mix. Get your most favourite record and put in on the decks from the start, and have a good listen, listen to all the sounds and write down what you think they are. Usually a record starts with the beat so that you can mix it in and also to build up the song.
Can you find the beat? If you cant they have a look at your feet or just see if you are nodding your head. If you find that you are tapping your foot or nodding your head then that is the beat doing that.

Listen to your chosen song carefully because you will find that its not always that clear to find a beat. After a short amount of time you will find that a sound will come in, maybe the bass, a hi-hat or a bass drum, anyway you will notice that a sound will occur a regular intervals. This is because each song follows a pattern along a beat structure. Nearly all dance music (house, progressive, trance, hard house) has 4/4 beat structures. This simply means that there are 4 beats per bar. Like I said before you will hear sounds at regular intervals, this will either be after 4 beats, 8, 16 or 32 beats.
Count the beats and you will see that after 4,8,16 or 32 beats a sound will come in, this is so on nearly every single dance song.
Knowing how the beat structures work will help your mixes tremendously, but more on that later when you have got your mixing more perfected.

Here are a few rules for mixing, if your good enough see if you can do all of them.

Basically beat matching/mixing consists of this: -

1) Aligning the beats per minute
2) Phrasing
3) Being able to mix under pressure or when you are live.

All tracks have a genre so this will help you structure your sets more easily if you know what sort of genre you are playing. More on set building later. Although knowing what sort of genre a song is, its more important to know what the BPM of the track is, BPM= Beats Per Minute. To work out the BPM of a track you could either count the beats yourself, counting for one minute or to buy a BPM counter.
With the knowledge of BPM's behind you and genre's, you must now learn how to match the two songs together.

Since you now the BPM's of some of your songs, start by playing one song at +2 on the left deck, and play another song with the same BPM on the other side, you should notice that they should be at the same pitch. If there not, that just means that the weights are different. Did you find that the pitch was nearly the same on each deck?

When beat matching you obviously need to get the beats in time. To do this start the song on the left deck and start the song on the right deck, in the headphones. To be able to beat match and mix you are going to need to be able to cue. With the song you want to mix in, put the stylus at the start of the record, and play it until the beat comes in. When the beat does come in, stop it with your hand. Keep moving the vinyl back and forward around this ONE beat. This is called cueing. When cueing you must do it in time with the beat, practice this for a little while until you get the hang of it.
When you do get the hang of it, cue in time with the music and follow this:

Left Deck: 1 2 3 4
Right Deck:- - - -

Where the dashes are is where you should be cueing in time with the beat. On the 5th bat let go of the cueing record & you should notice that they are in time for only a little while; if you know the BPM of the two records then you should know weather you should speed up the record or slow it down. If you don't then you will have to guess. When you are getting better at beat matching and mixing you will notice that you will be able to know weather to slow it down or speed it up.

Usually on your first couple of mixes it will be too slow. There are a few ways to speed up the record.

1) To move the record around using the label.
To do this put your finger on the label and give it a little push. Don't push too hard because your finger will either slip off the label and go across the vinyl (maybe scratching it) or will speed it up too much. While speeding up the record using your finger you will need to move the pitch at the same time, otherwise it will just speed up for that second and will go back to being out. If you do use this method to speed up the record, don't speed it up when you have got both songs mix out of the speakers because other people will hear it and think you cant mix.

2) Speed up the record using the spindle.
This method is just as good as the one above, except you move the whole platter and the record when doing this method of speeding up. Doing this is fairly easy but sometimes it won't speed up enough, or if you don't have enough strength it wont speed up at all. The same applies to this method as above, don't speed it up when mixing it in because it is extremely noticeable.

Obviously it's going to be the opposite just the same amount of times, to slow it down there are a few methods: -

1) Grabbing the spindle
Grabbing the spindle to slow it down isn't that easy because it tends to slow it down too much. Therefore you have too speed it up again. Basically you just hold the spindle till the beats are back in time. Isn't the best method to slow down a record but if you like using it then do?

2) Touching the platter.
This method works nice and well and is easy to do. All you have to do is LIGHTLY touch the platter and keep you finger on there till the beats are back in time. If you keep using this method for a long period of time, your finger can start to hurt. I know it sounds stupid but it can happen.

3) Lightly touch the side of the record.
All you have to do is to lightly touch the side of the record so that it slows down. If you touch it too hard it will either stop the record or slow it down. I use this method a lot and sometimes use the spindle method.

So just to recap.

Firstly get the song you want to mix in, at the start of the record (Cued)
Secondly count 4 beats then let go of the record.
If it's in time then good, if not slow it down or speed it up.

Extra Tips To Help You Mix & Beat Match.

1) Turning Up The Music
You may find it easier to mix if you turn up the music. I know that I find it a lot easier to mix when the music is loud. Its hard to mix when its quite because you cant hear the beats correctly. Only turn up the music within your limits, don't go disturbing the neighbours or busting a pair of speakers. I bust three pairs within a year, costs a lot of money I can tell ya.

2)Turning Down The Music
This may sound stupid but it can help by turning down the music. Firstly you can damage your hearing so then you cant hear the music very well and secondly you may have the music too loud and you can't hear the music in the headphones. This will then damage the headphones costing you money. Also if you have it too loud, the frequencies can sound weird. It may sound too high-pitched and not very bassy making it hard to beat match etc...

3) Changing The EQ's. Treble, Middle & Bass.
Fairly obvious this one. If you cant hear a sound in the music very well turn either the treble middle or bass up. Also going to other way, if a song is too bassy turn down the bass etc... Simple.

4) Moving Your Headphones
Moving them around your head can sometimes make the beats clearer. Another thing to try is to turn down the bass on one of the songs, it does work, but don't cut off the bass completely.

5)Turning Up The Headphones
When the music is quite it can be hard to hear the beat because you have the speakers too loud. Turn them up to hear the music better but not too loud that it damages your hearing or headphones.

6) Mixing Similar Songs
Easy this one. Mix songs that sound the same or are similar. Simple. Also mix songs with a long intro or songs with just a plain and simple beat. This little tip is very useful if you are just starting out.
Also try mixing the same song because they are exactly the same and should go together nicely.

7)
Moving The Speakers
This tip can be quite hard to do if you don't know what your doing. Basically in a room there are sound acoustics, which can either, enhance sound or do the opposite. If your speakers are in the wrong place the beats with sound our whether or not the beats are in time. This is because the sound is bouncing back off the wall at an odd direction and causing it to sound out of time. The only solution is to move your speakers around till you get a "dead" sound where it basically sounds normal. Also try moving things around in your room like tables etc... because that's what the sounds bounces off, material objects. Just move things around to get the best sound.

8) Staying Off Your Decks.
I bet your all thinking "what the fuck is he on about". Well its simple. If you go on your decks too much you will not only get board of them but frustrated and annoyed because you can't beat match or mix. Just simply take time our to chill and try not to get wound up.