Why do I get gibrish output to the serial monitor of my arduino mega 2560?
Your captured outputs look like either a MISO-MOSI inverted connection, a baud rate mismatch or a sync problem. Sequence of steps to diagnose this:


Check your serial settings: both sides should have the same configuration for data rate, parity, data bits and stop bits. 9600 baud/no parity/8 data bits/1 stop bit is a good starting point.
Set up both devices to a low, identical baud rate e.g. 9600 baud, then increase it if 9600 works. Push it up till a possible bottleneck at serial handling code or cabling / connections shows up. 
Switch the MOSI and MISO lines at any one device - if you get nothing at all then switch them back.


If all the above steps fail, please update your question with results observed.