What is the best way to redirect my naked domain?

One thing to keep in mind is that DNS does not provide a redirect - adding an A or CNAME record will only provide your IP address to people that type in that URL. If you only add one of these two records, www.example.com and example.com would both resolve to your web server, essentially giving each page on your site two addresses and potentially wreaking havoc with any statistics you're keeping.

You would have to set up an additional 301 redirect, via server-side redirects or the HTML redirects you were mentioning, before visitors would always be redirected to use the example.com version of your site.

The 301 redirect is what you want to use if SEO is your primary concern. The 301 redirect will not only tell the search engines your pages have moved (assuming you are currently using both the www and non-www versions of your pages) but also help them associate the old URLs with the new URLs. This means any links you have to your old pages will count towards your new pages. They do lose a little bit of value because of the redirect but that's better not not doing it at all.

See this answer for more info on 301 redirects and www/non-www