Easy way from the beginning:

Open synaptic: System –> Administration –> Synaptic Package Manager. Search for hp, locate “hplip-cups” right click, and “Mark for Installation”. Hit apply. Once finished, In synaptic find the hplip-gui, again “Mark for Installation”. Once completed you should be able to go to System –> Preferences –> and you should see HP Toolbox.

If  you had only installed the hplip-gui, you may have received this message after opening the HP Toolbox and attempting to add your printer:

It will stll add your printer, but you will be missing the scan/fax ability as seen below:

If this is the case, re-open Synaptic, search for hp, and install hplip-cups (there is nothing in the package description about this package having anything to do with faxing or the HP-Fax-hpcups.ppd.gz). This will add the necessary driver. If HP Toolbox is running  you will notice a blue HP button on your upper-right gnome-panel see image below:

Right click on it, and Open Device Manager. Select Device –> Setup Device, and go through re-discovering your same printer device. You should now be able to see the HP your model (Fax), it will look like below: