I am trying to use org-mode and whenever I press Crtl+return emacs does C-J instead. I know this because when I use c-h k and then press crtl+return, emacs shows: "It is bound to C-j." Is there anyway I can make it register ctrl+return so I can insert headings?
I am using emacs23 through the terminal on ubuntu 12.04 x64. When I do this on my windows machine it does insert a new heading.
Possibly. As @phils says, C-Enter is usually not a valid sequence for the vast majority of terminal emulators. This is because when you press a key, or key combination, the terminal sends a sequence of characters to the relevant application. Pressing a sends a, whereas Enter sends CR - carriage return (otherwise known as ^M, \r or \015).
What sequences are actually implemented in modern terminals is mostly just a hang-over from the earlier, physical, terminals that they emulate (notably the VT-100). These machines didn't allow the use of Ctrl in conjunction with every key, such as the function keys, for example, so C-F1 was not possible and didn't have an escape sequence defined. Similarly, there is no control sequence for C-Enter, so when you press it, the terminal ignores the Ctrl and just sees the Enter.
You may, however, be able to define your own escape sequences in your terminal, which you can then bind to the correct key combinations in emacs. See here, for example. I was able to use this method to be able to use C-Enter. Unfortunately, this is still a bit of a pain, as it requires a lot of configuration and you may still be unable to use some sequences (C-M-% doesn't work in konsole for me). As with @phils, I've taken to using the GUI, but I'd love to have better integration with my terminal.