I got a dedicated server from Limestone Networks. They provide free DNS hosting. So if I am entering the records through their "control panel", do I need to actually set up anything on MY server? I'm a bit confused...
I'm not sure what you mean by "the provide free DNS hosting." If you own a dedicated server you should setup your own nameservers and this is done via your registrar service, step after which you should ad to your server's named.conf file the corresponding A, CNAME, PRT and DNS records before rebooting and get your domain working on your server. As a temporary solution, however, you can point your domain name to your provider's nameservers and equally, add the corresponding records and entre to both named.conf and resolv.conf files
I think I've got it all set up.. My provider provides free DNS hosting so I manage my DNS through their nameservers...
If your host is providing free DNS, I'd recommend you go with them. It may sound simple to run your own DNS and just setup the usual A/CNAME records, but it isn't (I run my own DNS setup so I can tell you). Securing your own DNS servers, registering your nameservers, providing uptime, setting up SPF/DomainKey records etc. isn't simple and you can easily cause your site to be unavailable to users if these aren't setup correctly. Go with your own servers only if you know BIND well enough, have at least 2 servers you can run DNS on and would like to setup advanced things (like views or multiple master-slave configurations).