Let me start of by clarifying what Microsoft has already published, the Content Search Web Part is only available in Office 365 Plans E3, E4, A3, A4, G3, G4, E3 for non-profits. See the FAQ here – http://blogs.office.com/b/office365tech/archive/2013/10/29/search-innovations-for-site-and-portal-design-in-sharepoint-online.aspx
However, if you’re like me, you may have gone to a site to add the web part and not seen it even though it should be included by default.
So what gives? Apparently for some of us that already had Enterprise Features enabled on our site collections prior to Microsoft rolling this out in October 2013, it just didn’t get added to our web part gallery. The fix is actually quite simple. Go into your site settings, under Site Collection Administration, click on Site collection features and deactivate and then reactivate the SharePoint Server Enterprise Site Collection features
Now when you go back to add a web part to your page the Content Search Web Part will be available!
