Emission line diagnostic diagrams probing the ionization sources in galaxies, such as the Baldwin-Phillips-Terlevich (BPT) diagram, have been used extensively to distinguish AGN from purely star-forming galaxies. Yet, they remain poorly understood at higher redshifts. We shed light on this issue with an empirical approach based on a z~0 reference sample built from ~300,000 SDSS galaxies, from which we mimic selection effects due to typical emission line detection limits at higher redshift. We combine this low-redshift reference sample with a simple prescription for luminosity evolution of the global galaxy population to predict the loci of high-redshift galaxies on the BPT and Mass-Excitation (MEx) diagnostic diagrams. The predicted bivariate distributions agree remarkably well with direct observations of galaxies out to z~1.5, including the observed stellar mass-metallicity (MZ) relation evolution. As a result, we infer that high-redshift star-forming galaxies are consistent with having "normal" ISM properties out to z~1.5, after accounting for selection effects and line luminosity evolution. Namely, their optical line ratios and gas-phase metallicities are comparable to that of low-redshift galaxies with equivalent emission-line luminosities. In contrast, AGN narrow-line regions may show a shift toward lower metallicities at higher redshift. While a physical evolution of the ISM conditions is not ruled out for purely star-forming galaxies, and may be more important starting at z>2, we find that reliably quantifying this evolution is hindered by selections effects. The recipes provided here may serve as a basis for future studies toward this goal. Code to predict the loci of galaxies on the BPT and MEx diagnostic diagrams, and the MZ relation as a function of emission line luminosity limits, is made publicly available. ; Comment: Main article: 15 pages, 7 figures; Appendix: 13 pages, 11 figures. Revisions: Paper now accepted for publication in the Astrophysical Journal (same scientific content as previous arXiv version). IDL routines to make empirical predictions on the BPT, MEx, and M-Z plane are now released at https://sites.google.com/site/agndiagnostics/home/mex