It's practically always correct to use it without the preposition, so you'll be fine if you stick to that. One case where you must use the preposition is when you try to find info about something. In that case, "για" means "σχετικά"=about. Namely, "ψάχνω σχετικά με κάτι"
It is interesting that the discussion shifted to questions of English usage. From what I have found, the modern Greek verb "ψάχνω" is used without a preposition when it is equivalent to the English verb "search," for example, "they searched the room" ("έψαχναν το δωμάτιο"). However, it seems that modern Greek follows the same logic as English, if you want to say something like "I am looking for a friend of mine" ("ψάχνω για ένα φίλο μου"). In other words, you add the preposition "για".
My understanding is that κοιταζω and ψαχνω are not interchangeable because they do not mean the same thing. The verb κοιταζω is equivalent to the English verb "look" or "look at" or even "watch." For example, κοιτά πού πας ("look [or watch] where you're going.") The verb ψαχνω means "look for" in the sense of "search". Therefore, to use a minimum pair, if I ask τι κοιτάζεις; I mean "what are you looking at?" If I ask τι ψάχνεις; I mean "what are you looking for?" My further question to an educated Greek speaker is the following: Can you say για τι ψαχνεις and does it mean the same thing as τι ψάχνεις;?