As I could not find a way to perform searches on objects with many to many relations using Criteria API/Example, I came up with Example like HQL solution (pretty much untested):
Code:
   public Collection search(Session session, Object entity)
      throws Exception {
      SessionFactory sessionFactory = session.getSessionFactory();
      StringBuilder joinString = new StringBuilder();
      StringBuilder queryString = new StringBuilder();
      ArrayList queryValues = new ArrayList();
      ArrayList queryValueTypes = new ArrayList();
      Stack queue = new Stack();
      int tableSuffix = 1;
      String tableName = "t0";
      String fromString = "SELECT " + tableName + " FROM " + entity.getClass().getName() + " AS " + tableName;
      Object te[] = new Object[2];
      te[0] = entity;
      te[1] = "t0"; 
      queue.push(te);
      while (queue.isEmpty() == false) {
         te = (Object[])queue.pop();
         entity = te[0];
         tableName = (String)te[1];
         
         ClassMetadata metadata = sessionFactory.getClassMetadata(entity.getClass());
         Type propertyTypes[] = metadata.getPropertyTypes();
         String propertyNames[] = metadata.getPropertyNames();
         Object properties[] = metadata.getPropertyValues(entity, EntityMode.POJO);
         
         if (properties != null) {
            for (int i = 0;i < properties.length;i++) {
               Object property = properties[i];
               Type propertyType = propertyTypes[i];
               String propertyName = propertyNames[i];
               if (property != null) {
                  if (propertyType.isCollectionType() == true) {
                     // *-* or *-1
                     Collection collection = (Collection)property;
                     if (collection.isEmpty() == false) {
                        for (Iterator it = collection.iterator();it.hasNext() == true;) {
                           te = new Object[2];
                           te[0] = it.next();
                           te[1] = "t" + tableSuffix; 
                           joinString.append(" INNER JOIN " + tableName + "." + propertyName + " AS t" + tableSuffix++);
                           queue.push(te);
                        }
                     }
                  } else if (propertyType.isAssociationType() == true) {
                     // [0-1]-*
                     te = new Object[2];
                     te[0] = property;
                     te[1] = "t" + tableSuffix; 
                     joinString.append(" INNER JOIN " + tableName + "." + propertyName + " AS t" + tableSuffix++);
                     queue.push(te);
                  } else {
                     // attribute
                     if (queryString.length() > 0) {
                        queryString.append(" AND ");
                     }
                     queryString.append(tableName + "." + propertyName + "= ?");
                     queryValues.add(property);
                     queryValueTypes.add(propertyType);
                  }
               }
            }
         }
      }
      
      String fullQueryString = fromString + joinString.toString() + " WHERE " + queryString.toString();
      Query query = session.createQuery(fullQueryString);
      query.setParameters(queryValues.toArray(), (Type[])(queryValueTypes.toArray(new Type[queryValueTypes.size()])));
      
      return query.list();
   }
Unfortunate thing with above is, that HQL includes "join tables" once for every table join (joining table twice, causes 4 joins instead of 3; I guess it's something that sql compiler may optimize, but...)
Problem with Criteria was that it didn't allow multiple joins on same property, making it impossible to perform queries like: Find all documents which have been accessed by person A 
AND person B.
Example database in XML: 
Code:
<document>
 <person>
   <name>a</name>
 </person>
 <person>
   <name>b</name>
 </person>
</document>