Short bio: Computer Scientist, FOSS supporter (read more)
Tux Machines (TM)-specific
If you are a command line guru, you call upon your zypper, yum, conary, or apt-get from the terminal, and you awk sed grep your way to what you're after.
For me, unless I know exactly what package I want--and I often don't--I typically turn to Synaptic, the graphical package manager that graces my Ubuntu notebook. Synaptic is a really nice application, and I've spent untold hours nerdily sifting through the massive software catalog that Ubuntu inherits from Debian.
I've also used Synaptic to resolve unasked questions.