Clean and error free way
To do that you need to ensure your modules XML file is placed in your var/connect
folder. It must be named based on your module name for example: Vendor_Module.xml
and it contains all the info / requirements / files path of your module.
Then you go to the backend under System > Magento Connect > Package Extensions.
You choose "Load Existing Package" tab and choose your module in the list.
From here it will load all your modules information and you'll be able to edit the PHP requirement from the form.
Once you're done, save and generate the package, your module tgz and its corresponding XML file will be updated.
Quick and dirty way
Edit the package.xml
file, find the following XML node and edit it:
<dependencies>
<required>
<php>
<min>MIN</min>
<max>MAX</max>
</php>
</required>
</dependencies>