Improving a MySQL Search

I'm creating a serious of pages that show various aspects from a Syslog output. The main information is currently stored in one MySQL table - which after having been run for about 2 and a bit months has got nearly 1000000 records. With this amount of information, it's taking a large time to carryout even the simplest query. Someone has suggested I look at setting up an archive, for slower searches, and a more recent table for quicker searching, but I'm reluctant to do this, as it would take quite a bit of time to copy all the information across as it stands, and then also to run a cron which transfers between the live and archive. Can anyone suggest some quick easy methods for speeding up the search? Cheers James