Non so cosa intendi tu per "cercare su internet", ma Synaptic e Ubuntu Software Center cercano nei medesimi repository (ovvero quelli configurati in sources.list).