Not sure if I am doing this right, but does not work with either terminal, or
<Alt><F2>, when running 9.04.

I am running Ubuntu 9.10 am not sure if its in 9.04. But try this in
terminal mode/comand prompt :- type 'locate software-center' and see if
the program is listed (ignore quotes). If it does not show its not
installed on your machine and or not part of 9.04.

If not there then I think its very worth while installing and the best
way probably is to visit its web site (try a google search).

I have spent some time looking thru the programs it lists and it has
become one of my must haves.

Software Centre debuted with 9.10 and replaces Add and Remove... It is not
installed or available for 9.04. To get it you will have to upgrade.
Otherwise use Add and Remove...