I think you're talking about something like this. This is done by adding fields to the database's products table and submitting them as part of the form that goes to the advanced search page whose database query needs to be upgraded to handle them (on this site it was taken further and a new product type was built - you can see this if you click on one of the plans products and look at the URL - it clearly has a custom product info page).

There would also be work needed in the admin to allow manage which options are valid and to attach them to products.