You need to tell company-mode what backend to use. In my init file I have the following code

(add-hook 'go-mode-hook
      (lambda ()
        (set (make-local-variable 'company-backends) '(company-go))
        (company-mode)))

This was all that I needed to get completion.

You need to tell company-mode what backend to use. In my init file I have the following code

(add-hook 'go-mode-hook
      (lambda ()
        (set (make-local-variable 'company-backends) '(company-go))
        (company-mode)))

You will also need the gocode autocomplete daemon which you can get by executing go get github.com/nsf/gocode.