Well Garbage is at least something!
Have you got a common GND connection between Galileo and UNO as well as RX/TX ?
Of course Garbage can also be simply a wrong baud rate, so it might be worth double checking, and simply experimenting with changing the baud rate at one end.
I have connected the GND and still nothing happened. I have played with the baud rate on SoftwareSerial and the Galileo. I have even tried to use pins 0 and 1 of the Uno. Nothing has proved fruitful.
Take a look at the the wire.h library from the Arduino Website. http://arduino.cc/en/Tutorial/MasterWriter
I was able to communicate between an Arduino Uno and a Galileo. As well as two Galileo's. Just keep in mind that Galileo can only be used as Master not Slave.