Emacs 23 does not come with ELPA installed. The next version of Emacs (24) is going to have a package manager included by default (it is based on ELPA) that will allow you to use Marmalade. If you are using Emacs 23 (which you probably are if you installed from your distro's package manager) then you should use ELPA. If you installed Emacs from a nightly build then you can use Marmalade.
Sorry, you're right. I was confused by the ELPA page which lists instructions only for emacs 21 and 22, but says elpa will be included in the next version of Emacs. (edit: now I can't find where I read this. I'm incredibly confused.)
Now I'm confused about how my other installs have it working.