The emerging field of graph signal processing aims to develop analysis and processing techniques for data that is best represented on irregular domains such as graphs. To this end, important notions of classical signal processing, such as smoothness, band-limitedness, and sampling, should be extended to the case of graph signals. One of the most fundamental concepts in classical signal processing is the Fourier transform. Recently, graph Fourier transform was defined as a generalization of the Fourier transform on Abelian groups, and many of its properties were investigated. However, a graph is usually the manifestation of a non-commutative structure; this can be easily seen in the case of the Cayley graph of a non-Abelian group. In this article, we investigate a new approach to develop concepts of Fourier analysis for graphs. Our point of view is inspired by the theory of non-commutative harmonic analysis, and is founded upon the representation theory of non-Abelian groups.