I don't use Linode, but I have a couple VPSs. I think you'd be fine on the 512. You can always upgrade if you're outgrowing it.
i have setup a new site www.example.org (dummy name) on my linode VPS (i am using ubuntu 10) as below:
ServerAdmin [email protected]
I used to use linode and this is what I had in db file:
example.com. IN SOA li153-35.members.linode.com. foo.example.com. (
example.com. IN NS li153-35.members.linode.com.
example.com. IN NS ns1.linode.com.