Would like to understand what needs to be done to verify my app on Search Console (Webmaster Tools) so I can get impressions and clicks from App Indexing.
You have two options to accomplish this. You use the Search Console or you can use the Developer Console.
For using the Search Console approach, you need to have management rights on the app on Google Play and be logged in with that same account in Search Console. Here, you can add a new property for your app and specify the app's root URI in the supported format [android-app://{apk_package_name}/], similar as the following example:
android-app://com.example/
Next, the SC will verify if your account is the same as the app owner's Play account and automatically verify the app property. However, if your SC account is not the same as your Google Play, you can always ask the owner of the SC account to add you as an owner or user of the app property.
Then the process of validation can take up to 48 hours. You can see more information about this process in here - https://support.google.com/webmasters/answer/6178045
For using the Developer Console approach, you just need to send a request to the website webmaster. As soon as the webmaster approves your request, the process of validation will begin, lasting up to 48 hours as well. You can have more information about this approach in here - https://support.google.com/googleplay/android-developer/answer/6041489
These two approaches are all you need to do in order to get your content indexed, in the case that you use the HTTP scheme for your deep links. If instead you use a custom scheme, you still need to provide your deep links through the use of a sitemap or website annotations.