I'd suggest anyone in this situation try slicehost / ubuntu / nginx / fcgi as a starting point. Reasonably fast, low memory, slicehost is awesome and has awesome tutorials. I find nginx much easier to configure than apache. These articles should cover everything. You should pretty much be able to paste the code in, but consider what you are doing first.
http://articles.slicehost.com/2008/11/28/ubuntu-intrepid-set...
http://articles.slicehost.com/2009/3/5/ubuntu-intrepid-nginx...
http://stackoverflow.com/questions/605173/how-to-nginx-virtu... OR http://code.djangoproject.com/wiki/DjangoAndNginx
http://docs.djangoproject.com/en/dev/howto/deployment/fastcg...
I don't know the scope of your app, but if you're just starting out with Django, try Google App Engine. It's super scalable and it's easy to deploy. Also, take a look at this sample search app that runs on Google App Engine - the source code for it is on github and this link the guy goes into how he did it: http://lethain.com/entry/2009/mar/05/deploying-django-spring...
As about other hosting issues, I usually find django's official site to be pretty thorough: 1) http://docs.djangoproject.com/en/dev/howto/deployment/modwsg... 2) some hosts - http://code.djangoproject.com/wiki/DjangoFriendlyWebHosts 3) Amazon EC2 Django - http://blog.awarelabs.com/2008/amazon-ec2-basics-for-the-cur...
So I'd add 2b)some sysadmin knowledge: apache, config files, ssh, ...