HP Pavilions seem to work with Ubuntu; have worked in the past, too. There is some hardware that may require post-installation driver configuration (most probably the wireless local area network hardware), but nothing impossible/too hard. I installed Ubuntu 11.10 (also 11.04) a few months ago onto a brand-new Pavilion, without notable problems. WLAN did not work right out of the box, but after downloading and installing the drivers (easily obtained from the web free of charge; also good instructions were easily found, and LQ helps you out here) the situation was solved. If you pay a little attention to the WLAN hardware onboard, you can probably get around this problem by choosing the model wisely in the shop.
If you can, take the Ubuntu version you'd like (live CD, the usual installation disc) to the shop and ask if you can try it out there. In my experience most shops have nothing against this, and it allows you to see instantly whether or not the machine boots and works with the operating system.