What's the difference between these ones in function names? I can overwrite each one in template.php, so?
The functions whose name start with theme_ are theme hooks, while the functions whose name start with template_ are preprocess and process functions implemented by the module that implements the relative theme hook.
For example, theme_image() is a theme hook that renders an image. template_preprocess_node() is the preprocess function implemented by the Node module, which the module implementing the node theme hook. (See the first code lines of node_theme(), the hook_theme() implementation done by the Node module.) There are other modules that can implement a preprocess function for the node theme hook, but for those modules, that preprocess function is named
A theme can implement both a theme hook (see bartik_menu_tree()) and a preprocess function (see bartik_preprocess_node()). The difference is that
bartik_menu_tree() overrides the default implementation (theme_menu_tree()) when the current theme is the Bartik theme, while
bartik_preprocess_node() doesn't override
template_preprocess_node(), but it is executed after it. (See the documentation for theme().)
As for using two prefixes, the reason is to documenting the purpose of the function. Even if theme_ were used in both the cases, the difference between
theme_preprocess_node() would still be clear, but it would require you to read what follows theme_. With the current implementation, you just read the first word of the function name.