The literature on evaluation of expensive black-box function is quite vast and it is usually based on surrogate-model methods, as other people pointed out. Black-box here means that little is known about the underlying function, the only thing you can do is evaluate $f(x)$ at a chosen point $x$ (gradients are usually not available).
I would say that the current gold standard for evaluation of (very) costly black-box function is (global) Bayesian optimization (BO). user777 already described some features of BO, so I am just adding some information that might be useful.
As a starting point, you might want to read this overview paper 1.
There is also a more recent one .
Bayesian optimization has been growing steadily as a field in the recent years, with a series of dedicated workshops (e.g., BayesOpt, and check out these videos from the Sheffield workshop on BO), since it has very practical applications in machine learning, such as for optimizing hyper-parameters of ML algorithms -- see e.g. this paper  and related toolbox, SpearMint. There are many other packages in various languages that implement various kinds of Bayesian optimization algorithms.
As I mentioned, the underlying requirement is that each function evaluation is very costly, so that the BO-related computations add a negligible overhead. To give a ballpark, BO can be definitely helpful if your function evaluates in a time of the order of minutes or more. You can also apply it for quicker computations (e.g. tens of seconds), but depending on which algorithm you use you may have to adopt various approximations. If your function evaluates in the time scale of seconds, I think you're hitting the boundaries of current research and perhaps other methods might become more useful.
Also, I have to say, BO is rarely truly black-box and you often have to tweak the algorithms, sometimes a lot, to make it work at full potential with a specific real-world problem.
BO aside, for a review of general derivative-free optimization methods you can have a look at this review  and check for algorithms that have good properties of quick convergence. For example, Multi-level Coordinate Search (MCS) usually converges very quickly to a neighbourhood of a minimum (not always the global minimum, of course). MCS is thought for global optimization, but you can make it local by setting appropriate bound constraints.
Finally, you are interested in BO for target functions that are both costly and noisy, see my answer to this question.
1 Brochu et al., "A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical
Reinforcement Learning" (2010).
 Shahriari et al., "Taking the Human Out of the Loop: A Review of Bayesian Optimization" (2015).
 Snoek et al., "Practical Bayesian Optimization of Machine Learning Algorithms", NIPS (2012).
 Rios and Sahinidis, "Derivative-free optimization: a review of algorithms and comparison of software implementations", Journal of Global Optimization (2013).