"I search for his canary."

Translation: Eu caut canarul său.

[Motanu11]

Would "canarului" work instead of "canarul lui"?

[razvan.marin]

No. Canarului means canary's. Canarul lui means his canary.

[DornenEngel]

why is "caut pe canarul său" wrong?

[malena_2212]

Why there's nothing used for "for"?

[DornenEngel]

that was my question too, but answers are sparse nowadays.
I guess it is only used in the accusative constructions like: (eu) îl caut pe canarul lui
but I might be wrong :-)