จำนวนแพกเกจใน Debian มีมากมายมหาศาล เวลาที่ใช้ aptitude ติดตั้งโปรแกรม สิ่งที่ต้องการมากอย่างหนึ่งจึงเป็นเรื่องการสืบค้น โดยมากแล้วเรามักจะใช้ apt-cache ค้นหาแพกเกจที่มีคำค้นอยู่ในชื่อหรือคำบรรยายแพกเกจ แต่ความจริงแล้ว aptitude เองก็สามารถสืบค้นได้ไม่แพ้ apt-cache แถมยังค้นได้ละเอียดกว่าอีกด้วย

ถ้าอยู่ในหน้าจอ fullscreen ของ aptitude ก็สามารถเริ่มค้นได้โดยกดปุ่ม '/' ซึ่งจะปรากฎกล่องโต้ตอบขึ้นมาให้ป้อนคำค้น หรือถ้าจะค้นย้อนกลับก็ใช้ปุ่ม '\' แทน เมื่อพบรายการแรกแล้ว จะค้นต่อไปก็กดปุ่ม 'n'

ถ้าอยู่ที่บรรทัดคำสั่ง ก็สามารถสืบค้นได้ด้วยคำสั่ง

$ aptitude search query

โดยปกติ ถ้า query เป็นคำธรรมดา ก็จะเป็นการค้นหาแพกเกจที่มีคำที่ต้องการอยู่ในชื่อแพกเกจ (ไม่รวมคำบรรยายแพกเกจ) แต่ตรง query ที่ไม่ใช่คำธรรมดานี่แหละ คือความเก่งกาจของ aptitude