The theory of Newton-Okounkov bodies can be viewed as a generalization of the theory of toric varieties; it associates a convex body to an arbitrary variety (equipped with auxiliary data). Although initial steps have been taken for formulating geometric situations under which the Newton-Okounkov body is a rational polytope, there is much that is still unknown. In particular, very few concrete and explicit examples have been computed thus far. In this thesis, we explicitly compute Newton-Okounkov bodies of some cases of Bott-Samelson and Peterson varieties (for certain classes of auxiliary data on these varieties). Both of these varieties arise, for instance, in the geometric study of representation theory. Background on the theory of Newton-Okounkov bodies and the geometry of flag and Grassmannian varieties is provided, and well as background on Bott-Samelson varieties, Hessenberg varieties, and Peterson varieties. In the last chapter we also discuss how certain techniques developed in this thesis can be generalized. In particular, a generalization of the flat family of Hessenberg varieties constructed in Chapter 6, which may allow us to compute Newton-Okounkov bodies of more general Peterson varieties, is an ongoing collaboration with H. Abe and M. Harada. / Thesis / Doctor of Philosophy (PhD)