1) Prepositions rarely correspond one to one between languages.
2) German has the case system which often allows to omit a preposition where English needs one. (Here the accusative for the direct object, the dog.)
3) If you were to use a prepositional phrase, it'd be: Ich suche nach meinem Hund. (nach + dative)
4) Your solution in German sounds as if you were looking for something on behalf of the dog.