Even the popular registrars accept Bitcoin payments and offer free whois protection. All that is left is a temporary email address and not using your own IP.

I'd call that reasonably anonymous. Pay attention to the TLD, because it might be against ToS to register some of them anonymously (mostly ccTLDs). There's plenty that don't have such restrictions.

You probably want a registrar that accepts cash by mail.

Obviously do not do anything with US based companies. Find registrars and hosts that accept bitcoin. Find hosts that do not have to comply with DMCA and do not do so voluntarily.

Have a backup plan ready for when you get taken down.

A bit more detail: https://njal.la/ accepts cryptocurrency.

I like njalla. Would be nice to see some others taking their approach. Anyone know of others that embrace the idea that one should be able to register a domain name anonymously?

Buy with cryptocurrency, make sure your coins are not traceable to you.

Domains can be bought on njal.la, NameCheap, EasyDNS and many others.

Hosting can be bought on Simafri, Accu, and many many others.

Make sure you use Tor and VPN and NoScript throughout.

I had not heard of Simafri. Looks good actually.

It's true that you need a hosting provider in addition to a domain name. It's good to discuss privacy-enhancing domain name registrars and privacy-enhancing VPS providers in the same breath.

Use a cryptocurrency.