The computation of interfacial free energies between coexisting phases (e.g., saturated vapor and liquid) by computer simulation methods is still a challenging problem due to the difficulty of an atomistic identification of an interface and interfacial fluctuations on all length scales. The approach to estimate the interfacial tension from the free-energy excess of a system with interfaces relative to corresponding single-phase systems does not suffer from the first problem but still suffers from the latter. Considering d-dimensional systems with interfacial area L(d-1) and linear dimension L(z) in the direction perpendicular to the interface, it is argued that the interfacial fluctuations cause logarithmic finite-size effects of order ln(L)/L(d-1) and order ln(L(z))/L(d-1), in addition to regular corrections (with leading-order const/L(d-1)). A phenomenological theory predicts that the prefactors of the logarithmic terms are universal (but depend on the applied boundary conditions and the considered statistical ensemble). The physical origin of these corrections are the translational entropy of the interface as a whole, "domain breathing" (coupling of interfacial fluctuations to the bulk order parameter fluctuations of the coexisting domains), and capillary waves. Using a new variant of the ensemble switch method, interfacial tensions are found from Monte Carlo simulations of d = 2 and d = 3 Ising models and a Lennard-Jones fluid. The simulation results are fully consistent with the theoretical predictions.