We give detailed results on the existence and uniqueness for medians, means and minimax centers of probability measures on Riemannian manifolds, including the case when the probability measure is supported in a regular geodesic ball and the case of generic data points in a complete manifold. Some properties of Fr'echet medians are also given, such as statistical consistency and quantitative explanation of robustness. In order to compute the Riemannian medians and means, we develop deterministic and stochastic gradient descent algorithms. We show the convergence of these algorithms in regular geodesic balls. The rate of convergence and error estimates of these algorithms are also obtained. For probability measures with support in compact manifolds, partial simulated annealing is used to obtain processes which converge to the means. Simulation examples of our algorithms are also shown, in the case of Toeplitz Hermitian positive definite matrices coming from covariance matrices of autoregressive processes. Applications to signal detection are given.