I've gotten bitten by something similar to Todd's experience. Yesterday I wanted to install Privoxy on ProMEPIS. I downloaded the .deb from [link|http://www.privoxy.org|http://www.privoxy.org] but couldn't figure out what to do with it. I also tried using apt-get from memory, i.e. apt-get install privoxy without success. Yeah, I need to actually find the instructions rather than trying to guess my way through it. ;-) But some of this stuff should be discoverable by the user.
Xandros has an icon on the desktop called Xandros Networks. Inside is a menu item to "Check for New Software" or something similar. KDE and/or Gnome should have an easy to find icon or menu option for finding and installing software on the machine. If it's clear what to do simply by looking at the desktop, then the user will learn to use that and not go browsing for software until they know the system better.
Cheers,
Scott.