I have so much experience with this, you'll have to hang on to your seat. I'm posting this and then I'll edit it a zillion times with links and other goodness, so if it seems incomplete just refresh in a min or two.
As mentioned by Linguo, you should be able to run Skyrim. So here are some software tips.
Option one:
View this guide
The guide has a long list of almost everything possible to tweak in Skyrim. It will take awhile to go through it, but you can customize your game to give you the best performance while keeping decent graphics. One thing to note: the same author has a guide for configuring ATI Catalyst. Check that guide out as well.
Option two: mods and patches
Awesome mod
You should update Skyrim to the latest version, as the last two or three patches have seriously helped with the lag problems. The link above goes to a mod that helped me with my lag issues. Also as mentioned above, update your graphics driver. The last several Radeon updates have had Skyrim specific updates and upgrades in them, and they have helped a lot of people. You should be running 12.1 or the 12.2 preview drivers.
Get them here.
Option three: optimize
There are many guides out there to help a person optimize their computer; google some and start going through it. What you're looking for are ways to trim down your system without doing anything dangerous. Good things to do would be shutting off background programs, disabling services and processes, turning off unused gadgets, all those things. Be sure there are no programs in the background, like Firefox, Word, anti-virus programs, or instant messengers. Bad things to try without some experience: messing with the page file, editing BIOS settings, or registry editing.
Some easy things to try: right-click Skyrim.exe and go to properties. Under the Compatibility tab, check these four things:
Disable visual themes
Disable desktop composition
Disable display scaling
Run as Admin
Doing this will help slim Windows down while Skyrim is running, and when it isn't, your computer will be back to normal.
Also, try
Gamebooster. This program has helped me out a lot in the past. You can use it to defrag just your Skyrim directory (to help it run smoother) as well as shut off background processes, then turn them back on with a single click. Be sure and read a FAQ or tutorial on it if you're not sure how to use it- I seriously doubt you can break your system with Gamebooster, but I'll bet you could get a scare if you shut down Windows Explorer and don't know how to get it back.
Additionally, defrag your entire hard drive if you haven't done so in awhile.
CCleaner can be of help with fixing problems quickly and without much effort on your part- but make a restore point before running CCleaner, just in case. (To make a restore point, type "create a restore point" in the run box visible when you click the start button, or the Windows Orb as they are calling it these days.)
Other notes:
If you have too many save games, each time you try and load or save a game there will be lag. Delete old saves or move them to a new folder as a backup; you should stay under 50 saves to improve performance. By default, the saves are stored in "C:\Users\
user\Documents\My Games\Skyrim\Saves" for Windows 7, and similar directories for other OSs.
My suggestion: What finally made the game playable for me was going down a screen resolution; I hated to do it, but I gained between 8-20 fps when I dropped from 1600x900 to 1280x720. Also, shadows had a huge effect on my performance; drop them down a bit and see if it helps.