var api_friends_helper = require('./helper.js');
try{
    api_friends_helper.do_stuff(function(result){
        console.log('success');
    };
}catch(err){
    console.log('caught error'); //this doesn't hit!
}

And inside do_stuff, I have:

function do_stuff(){
    //If I put the throw here, it will catch it! 
    insert_data('abc',function(){
        throw new Error('haha');
    });
}

How come it never logs 'caught error'? Instead, it prints the stack-trace and the Error object to screen:

{ stack: [Getter/Setter],
  arguments: undefined,
  type: undefined,
  message: 'haha' }
Error: haha
    at /home/abc/kj/src/api/friends/helper.js:18:23
    at /home/abc/kj/src/api/friends/db.js:44:13
    at Query. (/home/abc/kj/src/node_modules/mysql/lib/client.js:108:11)
    at Query.emit (events.js:61:17)
    at Query._handlePacket (/home/abc/kj/src/node_modules/mysql/lib/query.js:51:14)
    at Client._handlePacket (/home/abc/kj/src/node_modules/mysql/lib/client.js:312:14)
    at Parser. (native)
    at Parser.emit (events.js:64:17)
    at /home/abc/kj/src/node_modules/mysql/lib/parser.js:71:14
    at Parser.write (/home/abc/kj/src/node_modules/mysql/lib/parser.js:576:7)

Notice that if I put the throw RIGHT AFTER the do_stuff(), then it will Catch it.

How can I make it catch, even if I put it nested inside another function?

This is one of the downsides of using Nodejs. It basically has two methods on which errors are handled; One through using the try/catch blocks, and other by passing the first argument of every callback function as an error.

The problem is because of the event-loop asynchronous model. You can use the 'uncaughtException' event to catch errors that were not caught, but it has a become an usual program paradigm in Node.JS to use the first argument of the callback function to show if there any errors, as such: (I never used MySQL with NodeJS before, just making a general example)

function getUser( username, callback ){
    mysql.select("SELECT username from ...", function(err,result){
        if( err != null ){
            callback( err );
            return;
        }

        callback( null, result[0]);
    });
}    

getUser("MyUser", function(err, user){
    if( err != null )
        console.log("Got error! ", err );
    else
        console.log("Got user!");
});