In addition to the Spotify Android SDK already linked, you will also need to make use of Spotify's web API to perform searches. To do that simply build a URL based on the search parameters. For example, if I want to search for tracks called "riptide", I would use this url: https://api.spotify.com/v1/search?type=track&q=riptide. Full documentation for the web API is here: https://developer.spotify.com/web-api/
If you follow that first link, you'll see a huge blob of JSON output. Each track is an object within a JSON array called "items". Your app will need to open the url, parse that output, and decide what to do with it. If you don't know about parsing JSON, here is a good beginner tutorial: http://www.androidhive.info/2012/01/android-json-parsing-tutorial/
To actually play the track, you will need to get the value for the json key "uri" for each track; this is a String that can be passed into the play() method from the Player class in the Spotify Android SDK.
Your question is pretty broad, so I suggest you start with Spotify and then look into the other music services.