Here is a super simple way to think about it: The Hochshcild cochains on A is derived Hom over A \otimes A^{op} of A into A. This has two multiplications, given by composition and multiplication in the target respectively.
These commute, or intertwine, so the result has an action of the tensor product of two A-infinity operads, which is (at least if you chose the right A-infinity operads) an E_2 operad.