Which registrar

For what it's worth, you can use Linode's rather awesome DNS hosting service if you want to. You'd still need a registrar, of course, but you'd delegate the domain to Linode's nameservers and manage DNS through Linode. Or don't use it; whatever. But if you do, it removes DNS hosting as a factor when considering registrars.

Linode doesn't have an officially-recommended registrar. Go Daddy is the most popular – and, of course, most-hated -- in the world. Aside from that, 'round here, I'd say people use Namecheap, Name.com and NearlyFreeSpeech.net (which is really a web host).

Of course, what registrar is best also depends on what TLDs you're interested in.

There are also several other threads on this subject around here.

Probably the most extensive forum discussion: Who's a good domain registrar?

Every registrar will allow you to set the authoritative nameservers, which is all you need from them to use Linode's DNS. Of course, you could choose to use your registrar's DNS if they offer it (or someone else's entirely, for that matter).

Edit: to use Linode's DNS, at your registrar you would designate at least two of ns1.linode.com, ns2.linode.com, ns3.linode.com, ns4.linode.com, and ns5.linode.com as nameservers.