Basic method of optimizing hyperparameters
Hyperparameter optimization follows the same rules as model selection. Each set of hyperparameters effectively represents a different model you are considering, so the data you use to fit the model with some set of hyperparameters needs to be different from the data you use to evaluate which set of hyperparameters you want to ultimately use. A common approach for evaluating hyperparameters is nested cross-validation. This basically means that you need to treat hyperparameter selection as part of your model training process, and when you evaluate your model you evaluate the entire process front to back, i.e. treating hyperparameter tuning as a component of model training with respect to cross-validating over your training process. There's an excellent discussion of this in section 7.10.2 ("The Wrong and Right Way
to Do Cross-validation") of Elements of Statistical Learning, which you can read online and/or download for free. The general idea is that if you're not careful, you can actually overfit to your evaluation data. Play with this demo to see for yourself.

But yes, your intuition is correct. Hyperparameter tuning is often very computationally expensive. One way people sometimes try to minimize this cost is by limiting the search space of feasible parameters to a small discrete set, e.g. grid search. Another approach is to use guassian processes or KDEs to approximate the cost surface in parameter space. You can even use a multi-armed bandit approach. 

Frankly, you can really use pretty much any non-linear optimization technique for hyperparameter tuning, as long as you follow the appropriate cross-validation rules. The trick is figuring out bang-for-your-buck in terms of how much time/effort/compute you are willing to expend exploring parameters vs. the potential improvement to your model. Additionally, there are concerns about the limits of repeated cross-validation/holdout evaluations, but that's a whole other rabbit hole.