In gNewSense, package management is handled using the Debian GNU/Linux package management system (gNewSense packages are usually from Ubuntu, most of which are ultimately from Debian). Package maintainers create source and binary packages for many programs, from a variety of sources; this means most programs can be installed or removed in a single step.
gNewSense-KDE uses Adept for package management. Adept can be found in the System section of the K Menu. When you open Adept, kdesu will prompt you for your password. To find a package, use the search bar at the top, next to "Search: ". You can also narrow your search with the checkboxes; for example, you can specify whether the package(s) you are looking for are already installed.