CiviCRM can extend things like relationships, activities, etc. with custom data. It would be nice if the advanced search and/or search builder allowed this to be searched. This should be coordinated with a possible CRM_Contact_BAO_Query rewrite.
As per email exchange with Colin Sagan (a use case):
So, what you'd like to be able to do is to go to Advanced Search, scroll down to Relationships, choose the type, and then be presented with a form to fill in that relationship type's custom fields? (And be able to save that search as a smart group.)
That is correct. I am not as concerned with having the custom fields be visible only when selecting a specific relationship type in the advanced search page. It would be fine to just list all of the custom data fields from any relationship together. In some ways this would actually be preferable in case the user wants to create a smart group based on custom data from two different relationships types.