In this paper, we first focus on the sum of powers of the first n positive odd integers, T[subscript k](n)=1[superscript k]+3[superscript k]+5[superscript k]+...+(2n-1)[superscript k], and derive in an elementary way a polynomial formula for T[subscript k](n) in terms of a specific type of generalized Stirling numbers. Then we consider the sum of powers of an arbitrary arithmetic progression and obtain the corresponding polynomial formula in terms of the so-called r-Whitney numbers of the second kind. This latter formula produces, in particular, the well-known formula for the sum of powers of the first n natural numbers in terms of the usual Stirling numbers of the second kind. Furthermore, we provide several other alternative formulas for evaluating the sums of powers of arithmetic progressions.