You must already have custom firmware installed on your PSP.
To check if you have CFW go to Settings » System Settings » System Information.

If you are installing any firmware past 3.60 M33 you MUST UPGRADE first to 3.52 M33, and then 3.52 M33-3 to be allowed to upgrade. The only way to bypass this is to use Despertar Cementerio which requires a Pandora battery.

3.90 M33 Custom Firmware Upgrade Tutorial

• Visit dark-alex’s website to get the latest custom firmware version
  » 3.90 m33 Download | Mirror Download
  » 3.90 Original Sony Update Download

• After downloads are complete, extract(unzip) 3.90m33.rar and 3.90.rar files anywhere on your pc. you need to download and install winrar to extract .rar files
  » copy 390.PBP file into UPDATE folder

• Connect your PSP to PC via USB connection
  » Settings > USB Connection

• Copy UPDATE folder to your \PSP\GAME\

• Exit PSP USB connection mode

• Go to GAME > Memory Stick > PSP Update ver. 3.90
  » your battery must be at least 70% charge to proceed update, otherwise press L Trigger + Triangle after pressing X (cross) on the CFW Update Screen to bypass the battery check.
  » read and follow the steps carefully
  » Your PSP will shutoff / restart automatically after update is done.
  » Turn on your PSP and check again your Firmware version.

3.90 M33-X Custom Firmware Update
where X is the release number (e.g. 3.90 m33-2)

• Same instruction as above but with some few changes
  » Download 3.90 m33-2 Update, | Mirror Download
  » No need to download 3.90 Original Sony Update
• Or if you have WiFi access you can use the Network Update Tool of your PSP to update to the latest Dark_Alex custom firmware update. (for 3.80 M33 and above only)

NEW PSP 4.01 M33-2 Custom Firmware Upgrade