To do this, login to the Portal admin interface and click on the Setup menu at the top.
On the left menu that appears, click on "Managed Object Attributes".
This will show a list of attributes and how they are mapped to Identity Manager attributes. There is also a "Searchable" field here which must be checked to be available in searches. At the bottom of this list, you can click "Add User Attribute" to add a new attribute and have it available in searches.