In order to search a mailbox, the account you are using must be a member of the “Discovery Management” role group.

To check:
[PS] >Get-RoleGroupMember “Discovery Management”

To add somebody to a role:
When you add somebody as follows, you will prompted for the member. For example, Administrator.
[PS] >Add-RoleGroupMember “Discovery Management”

If you are doing this as Administrator and are adding the Administrator account, you will need to restart your EMS (Exchange Management Shell).

Once you have added the role, you will be able to use the Search-Mailbox cmdlet. There are many search options. Below is a simple example searching the subject of a mailbox. The way this works is that the search results are sent to a target mailbox and folder.

[PS] C:\> Get-Mailbox alias | Search-Mailbox -SearchQuery {Subject:”searchfor“} -TargetMailbox mailbox -TargetFolder “foldername

Example:
[PS] C:\> Get-Mailbox jim | Search-Mailbox -SearchQuery {Subject:”work rules“} -TargetMailbox mailadmin -TargetFolder “SearchJim

So, in this example, the mailbox jim will be searched for any message with “work rules” in the subject line. Any results, will be put in the mailadmin’s mailbox in a folder called SearchJim.

You can do the same thing for the body of the message:
-SearchQuery {Body:”somethinginthbody”}

Or a date range, except you have to specify sent or received:
-SearchQuery {Received:(1/1/2010..12/31/2010)}
-SearchQuery {Sent:(1/1/2010..12/31/2010)}

Or if you want to search for more than one criteria:
[PS] C:\> Get-Mailbox alias | Search-Mailbox -SearchQuery {Subject:”searchfor” AND Body:”searchsomethingelse” AND Sent:(01/01/2010..12/31/2010)} -TargetMailbox mailbox -TargetFolder “foldername

To search To or From with a date with an estimate instead of copy to TargetMailbox:
Search-Mailbox alias -SearchQuery {Sent:(01/01/2015..12/31/2015) AND To:user1@domain1.com AND From:user2@domain2.com} -EstimateResultOnly