I think this is a combination of joining and grouping. You basically want something like
<xsl:for-each select="listing/venueList/venue">
<xsl:variable name="events" select="listing/eventList/event[@venueId=current()/@venueId]"/>
<xsl:variable name="titles" select="/listing/titleList/title[@titleId=$events/@titleId"/>
<xsl:for-each-group select="$titles" group-by="category/categoryName">
<venue id="@venueId">
<category><xsl:value-of select="current-grouping-key()"/></category>
<xsl:apply-templates select="current-group()"/>
</category>
</venue>
xsl:for-each-group is XSLT 2.0; if you have to use 1.0 the syntax is much clumsier, search for "Muenchian grouping".
Note also that the join can be speeded up using xsl:key if your data volumes are large.
Michael Kay
http://www.saxonica.com/
Author, XSLT Programmer's Reference and XPath 2.0 Programmer's Reference