Beatmatching is the most important thing to learn.  You really need to concentrate on this above all else until you're fairly happy with your abilities.  Obviously it's a lot more fun banging the cross-fader around and being generally flash, and it's good to mess around with this from time to time to make things a bit more interesting - it can be a lot of fun.  However, don't forget that your priority should be learning to beatmatch, because if you can't do this, it won't matter what other tricks you've got up your sleeve things almost certainly won't sound very good.  The unfortunate thing is that this is most hard indeed to learn - well it was for me anyway, and at two years since I got my decks I can still find myself struggling with this from time to time.  There's no magic way to learn either, so you just have to persevere.  If you don't want to go insane with frustration, you have to learn to spot even the smallest improvements in your abilities, otherwise you'll feel like your going nowhere slowly and probably loose interest.

If you've mastered starting the record you're cueing on the first beat of a bar and can push and pull it to momentarily speed it up or slow it down, then you've already got the technical abilities you need.  All you need to do now is to develop an ear for what's going on and get the hang of using the pitch control.

At first you'll probably be listening to a confusing horrible mess going on in your headphones and you won't have a clue what's going on.  Do not despair, as things should get better with practice.

To beatmatch two tunes, put one of them on so it's playing over the speakers.  Put the next tune (cueing record) on the other deck and set the mixer up so that you can hear this one over the headphones.  You want to make sure that they are close enough in tempo such that you can actually beatmatch them - if you try and match a 120bpm tune with a 180bpm tune you will find that your pitch controls don't go far enough.  Start the cueing record on the first beat of an 8 bar chunk so that it lines up with the first beat of the playing record.  You've then got to use your pushing and pulling skills to keep the two records running at the same tempo.  If you're having to push the cueing record constantly to keep it up with the playing record, you need to speed it up using the pitch control.  The more you're having to push it to keep them at the same tempo, the more the pitch control has to be moved.  Obviously it's the same principle if you're having to slow down the record, but this time you need to use the pitch control to slow the record down.  This is an iterative process, it will take a long time for you to learn to move the pitch control to the right place pretty much stright away. 

When you're learning, you'll be going too fast, then too slow, then too fast etc etc...you'll almost certainly find that the record playing over the speakers will finish before you've got the cued record even vaguely matched up.  In fact you might have to put it back to the beginning quite a few times.

It really is a good idea to practice with different records and see how you get on, only reverting to your two copies of the same record if things are getting desperate.  What you should find is that slowly you get the hang of hearing which record is going faster or slower and by how much and learn how much you need to move the pitch control to get the tempos matched.