It has been a while since I did the install.
I downloaded the complete set of Debian CDs.
I booted the HP and hit enter at the prompt:
"To discontinue, press any key within 10 seconds"
At the menu that appeared I type SEA(rch) to find bootable devices.
This indicated my CD drive was path P0.
I then typed PA(th) to see what it had and saw it had the CD as my ALT(ernate) boot path.
I then typed BO ALT (boot alternate) to boot from the CD and the install progressed from there.
This worked fine except that it wouldn't start X on the console. Since I ssh in from a Windows box running PuTTY I've not really delved into what it doesn't like about video on the console. It does text fine on the console so is there for reboots which is the only time I really need the console.
I originally did that with Woody (3.0 r1) and later with Sarge (3.1 r2). I don't recall having any issues getting it to install either of these but may be forgetting something.
As I recall you can just download the install CD then install the rest using aptitude or apt-get. I prefer to have the whole set for later reinstall which is why I downloaded everything instead of doing it that way.
A link that talks about PALO in reference to Linux is: