Considering that the conventional channel interpolation method with sparse and irregular spaced pilots will lead to an error floor in underwater acoustic (UWA) orthogonal frequency division multiple access (OFDMA) uplink communications, a method for sparse channel estimation and pilot optimization is proposed in this paper. A compressed sensing (CS) algorithm is utilized for sparse channel impulse response estimation, which performs well in sparse and irregular spaced pilots and significantly decreases the channel estimation error. Besides, the pilots’ pattern and power joint optimization algorithm based on the random search technique is proposed for the minimum mutual coherence criterion in CS theory, which further improves the performance of CS estimation algorithm. During each iteration step, we randomly pick a pilots’ pattern from the subcarrier index set and a pilots’ power subset from the available power set. Then we perform this step iteratively within a certain searching time. Finally, the local optimal solution of the objective function for minimizing mutual coherence is considered as the feasible pilots’ pattern and power. Simulation results show that the convergence performance of the pilots’ pattern and power joint optimization algorithm is much better than that of the pilots’ pattern optimization algorithm. Furthermore, the channel estimation error of the proposed method is much lower than that of conventional least-squares channel estimator based on linear interpolation, CS channel estimator without pilot optimization, and CS channel estimator merely with pilots’ pattern optimization in channels of different multipath delay spreads. Finally, performance of the proposed method is demonstrated in the UWA uplink OFDMA systems with interleaved and generalized carrier assignment schemes respectively in the two-user case in a pool experiment. Experimental results show that the proposed method decreases dramatically the bit error rate in both carrier assignment schemes, and simultaneous reception for two users is achieved when signal noise ratio is larger than 10 dB.