Send AT commands to ESP8266 from Arduino Uno via a SoftwareSerial port
Does anyone know if what I am trying to do is possible?


Absolutely possible :)


  And if it is, what am I doing wrong?


SoftwareSerial isn't capable of 115200 baud rate (despite "allowing" this as a setting).  Some reports suggest as high as 57600 is workable, though in my experience 9600 is best for reliability.  How to change the baud rate on the ESP8266 will depend on the firmware version.  I've had success with AT+IPR=9600.  You only need to run this command once (it's a persistent setting).  I'd suggest, based on your description, that this is the most likely culprit that's causing the "garbage" output you describe.

A couple of other notes:


The ESP8266 runs on 3v3, not 5v, so you shouldn't have it directly connected to the digital pins—you need to run through a logic level converter.  Running 5v can fry your ESP8266.
The Arduino's 3v3 output has insufficient current to support the ESP8266 reliably (50mA Arduino vs up to 300mA for the ESP8266 by some accounts)—try running the ESP8266 off a separate supply.  It probably won't affect simple commands like AT but when you try to connect to a network etc. it may cause unexpected device resets.
As noted by others, you need to send \r\n — so make sure your Serial window is set to send both (this is a drop-down in the serial window)