The Modularity Theorem says every elliptic curve over $\mathbb{Q}$ can be gotten from the classic modular curve $X_0(N)$ by a rational map. Here $N$ is the conductor, easily calculable from a polynomial for the curve. Are the coefficients of the map calculable?
Unless this has changed lately, the proofs rely on some non-effective results. For example, Brian Conrad's comment at
Can you get Siegel's theorem "for free" from modularity and Mazur's Eisenstein Ideal paper?
points out that proofs of the modularity theorem (at least at that time) use the Shafarevich conjecture, which was proved by Faltings as a consequence of the once Mordell conjecture — now Faltings's theorem.
At least up to Levin http://arxiv.org/abs/1109.6070 the Shafarevich conjecture is not (yet) effective. But I do not know how that conjecture is used for Modularity. See also Damian Rössler's comment at Effective proofs of Siegel's theorem using arithmetic geometry.
To clarify: effective proof is not the same thing as constructive proof. As Noam Elkies's and Qiaochu Yuan's answers say this theorem is effective because you can calculate the coefficients once you know the curve is modular, so the relevant searches will return results. A constructive proof would also require effectiveness at each step to show all the relevant searches indeed return results. That would be a further question.
Best Answer
Yes. Once you know $E$ is modular, a dominant map $\varphi: X_0(N) \rightarrow E$ can be computed effectively. That's because one can effectively compute (a bound on) $\deg\varphi$.
Of course you need to compute a model for $X_0(N)$ for the question to make sense, but we know how to do that and to write $q$-expansions for the coordinates.
By integrating the $q$-expansion of the modular form associated to $E$, and using the Weierstrass model of $E$, you can find $q$-expansions of the functions $x$ and $y$ on $E$ to arbitrary precision. This is already implemented in gp, see elltaniyama.
Once you have $x$ and $y$ to enough precision you can solve linear equations in undetermined coefficients to recognize $x,y$ as rational functions in your coordinates on $X_0(N)$.