How to say "beginning of the month?" I've tried google translate, but it doesn't seem like what I'm trying to translate is quite right (at least I'm not sure if it's correct).

To say "end of the month", I have heard people say "这月底“，but is there a complement to that for "beginning of the month"?
There are lots of translations. What @agriprop said is probably the most common translation----月初----both in spoken and written Language. 

月初 对应着 月末,月底(end of month)

What @CA55CE37 answered should not have 本, here 本 means this month. You cannot use it to describe other month. However 月起 is not a word. I never heard. While 伊始 is a very formal word that we often used in written Chinese. 伊始 means the beginning. 伊始 is often used as adverb to describe that we begin to do something. The usage of 伊始: verb+伊始----the beginning of doing something.

refer:


http://www.nciku.com/search/zh/detail/%E6%9C%88%E5%88%9D/52961
http://www.zdic.net/c/8/94/168956.htm