This is actually simple to implement -- whenever vim changes mode, apply the current theme for the current mode. However, I don't think vim provides events for all events. For example, vim has InsertLeave and InsertEnter events but doesn't have any others (like ReplaceEnter, CommandEnter, etc). Do you have any ideas on this topic?

Does this snippet work for you? (just put it in vimrc)

if exists(':Tmuxline')
  augroup airline_tmuxline
    au!
    au InsertEnter * Tmuxline airline_insert
    au InsertLeave * Tmuxline airline
  augroup END
endif

Your snipped did not work. But if I use only this:

au InsertEnter * Tmuxline airline_insert
au InsertLeave * Tmuxline airline

It works. I will leave that in my .vimrc for now.
I know vim does not have a way to detected visual mode. Still, I have seen it is possible. Airline and Powerline actually do it, so I guess there is a way. Do you know of an easy way to do it?
I believe this code should be in tmuxline.vim. Or at least in README, so people can easily configure it.

Oh, I just realized that if I am not using Tmux than that gives me an error on Vim... I will have to work harder.

Ok, I fixed it. This is what I had to do.
As .vimrc is ran before any plugin is loaded, checking for :Tmuxline in it does not work. So I added an autocmd to verify that on vimenter event, like so:

function! AddTmuxline()
  if exists(':Tmuxline')
    augroup airline_tmuxline
      au!
      au InsertEnter * Tmuxline airline_insert
      au InsertLeave * Tmuxline airline
    augroup END
  endif
endfunction
au VimEnter * :call AddTmuxline()

This is now working.

I still would like to have visual mode working. I am accepting suggestions. :)

Ok, I have worked a little harder and found a script that works on .vimrc:

" change status on tmux
function! AddTmuxlineStatus()
  if exists(':Tmuxline')
    augroup airline_tmuxline
      au!
      au InsertEnter * call SetInsert()
      autocmd InsertLeave * call SetNormal()
      vnoremap <silent> <expr> <SID>SetVisual SetVisual()
      nnoremap <silent> <script> v v<SID>SetVisual
      nnoremap <silent> <script> V V<SID>SetVisual
      nnoremap <silent> <script> <C-v> <C-v><SID>SetVisual
      autocmd CursorHold * call SetNormal()
    augroup END
  endif
endfunction
function! SetInsert()
    Tmuxline airline_insert
endfunction
function! SetVisual()
    set updatetime=0
    Tmuxline airline_visual
    return ''
endfunction
function! SetNormal()
    set updatetime=4000
    Tmuxline airline
endfunction
au VimEnter * :call AddTmuxlineStatus()

I still believe this should actually be on the plugin, not on .vimrc.

Thanks for sharing the snippet!

I don't feel like this is in the scope of tmuxline though.

Is there no way to change it in Replace mode too? There isn't a theme, but you can initialize it to have replace colors with vim-airline in your vimrc. I just don't know how you could make it change to those colors on the fly. Here's what the README for vim-airline says:

* configure which mode colors should be used in tmux statusline >
  let airline#extensions#tmuxline#color_template = 'normal' (default)
  let airline#extensions#tmuxline#color_template = 'insert'
  let airline#extensions#tmuxline#color_template = 'visual'
  let airline#extensions#tmuxline#color_template = 'replace'

By the way, thanks for that snippet @giggio. I couldn't figure this out for the life of me. I'm hoping there is a way to make it work for replace mode too though.

Actually, I found a way to use Replace mode by making a simple change to @giggio's script above and one of the airline themes included with tmuxline. I literally replaced two words in the theme file. It might be nice to have that included with tmuxline. Here's the code:

    " change status of Tmuxline when Vim mode changes
    if exists('$TMUX')
    function! AddTmuxlineStatus()
        if exists(':Tmuxline')
        augroup airline_tmuxline
            au!
            au InsertEnter * call SetInsert()
            au InsertChange * call SetInsert()
            autocmd InsertLeave * call SetNormal()
            vnoremap <silent> <expr> <SID>SetVisual SetVisual()
            nnoremap <silent> <script> v v<SID>SetVisual
            nnoremap <silent> <script> V V<SID>SetVisual
            nnoremap <silent> <script> <C-v> <C-v><SID>SetVisual
            autocmd CursorHold * call SetNormal()
        augroup END
        endif
    endfunction
    function! SetInsert()
        if v:insertmode == 'i'
            Tmuxline airline_insert
        else
            Tmuxline airline_replace
        endif
    endfunction
    function! SetVisual()
        set updatetime=0
        Tmuxline airline_visual
        return ''
    endfunction
    function! SetNormal()
        set updatetime=4000
        Tmuxline airline
    endfunction
    au VimEnter * :call AddTmuxlineStatus()
    endif   " exists('$TMUX')

Then I created a file called airline_replace.vim in the following directory: .../tmuxline.vim/autoload/tmuxline/themes. The contents of this file are as follows:

    fun! tmuxline#themes#airline_replace#get() abort
      if !has_key(g:, 'airline_theme')
    throw "tmuxline: Can't load theme from airline, g:airline_theme isn't defined. Is airline loaded?"
      endif
      if !has_key(g:, 'airline#themes#' . g:airline_theme . '#palette')
    throw "tmuxline: Can't load theme from airline, 'g:airline#themes#" . g:airline_theme . "#palette' isn't defined. Is airline loaded?"
      endif

      let mode = 'replace'
      let mode_palette = g:airline#themes#{g:airline_theme}#palette[mode]
      return tmuxline#util#create_theme_from_airline(mode_palette)
    endfun

@giggio (and @JordanTHarris) thanks for the script. The only minor issue I was seeing was that when switching to visual mode Vim's status bar wouldn't update until I actually started selecting some text :

I didn't dig enough to understand why, but it has something to do with that return '' because without it the mode switch is instant... but it's also what prevented the cursor from annoyingly jumping to the beginning of the line after switching to visual mode.

Using return 'lh' fixes this :

function! SetVisual()
    set updatetime=0
    Tmuxline airline_visual
    return 'lh'
endfunction

Any way to do this with gruvbox? Using the extension the tmux is changed properly, but it won't change when trading of vim modes. I can't find the equivalent of airline_insert to gruvbox.

@jdurand Similar solution is mentioned in the comment in this SO answer:

If you add that return '' call as I suggested, then before the color updates a key needs to be pressed. This is a little hacky, but at the end of each nnoremap line you can just add <left><right>.