Groundwater model predictions are often uncertain due to inherent uncertainties in model input data. Monitored field data are commonly used to assess the performance of a model and reduce its prediction uncertainty. Given the high cost of data collection, it is imperative to identify the minimum number of required observation wells and to define the optimal locations of sampling points in space and depth. This study proposes a design methodology to optimize the number and location of additional observation wells that will effectively measure multiple hydrogeological parameters at different depths. For this purpose, we incorporated Bayesian model averaging and genetic algorithms into a linear data-worth analysis in order to conduct a three-dimensional location search for new sampling locations. We evaluated the methodology by applying it along a heterogeneous coastal aquifer with limited hydrogeological data that is experiencing salt water intrusion (SWI). The aim of the model was to identify the best locations for sampling head and salinity data, while reducing uncertainty when predicting multiple variables of SWI. The resulting optimal locations for new observation wells varied with the defined design constraints. The optimal design (OD) depended on the ratio of the start-up cost of the monitoring program and the installation cost of the first observation well. The proposed methodology can contribute toward reducing the uncertainties associated with predicting multiple variables in a groundwater system.