Array of structures: assignment from incompatible pointer type

There are several problems here.

First of all, I'm assuming that the purpose of this code is to allocate and initialize a single object of type struct node; as such, new_node is superfluous; it serves no purpose. Just get rid of it completely and return new_key directly.

Secondly,

new_key  = malloc(sizeof(new_key));

won't allocate enough memory to store an object of type struct node; it only allocates enough space to store a pointer to struct node, because the type of the expression new_key is struct node *. You'll want to change that line to

new_key = malloc( sizeof *new_key );

Note that sizeof is an operator, not a function; parens are only necessary if the operand is a type name like int or float or struct whatchamacallit.

Finally, the line

new_key->data = value;

is a red flag; depending on how you call NewNode, this pointer may wind up being the same for all of your nodes. If your caller looks something like:

while ( not_done_yet )
{
  x = get_input();
  node = NewNode( &x );
  root = insert( root, node );
}

all of the nodes in your tree will wind up pointing to the same thing (x). Worse yet, if x goes out of scope, then suddenly all those pointers become invalid.

If your node is meant to store a single integer value, then it's better to make both the parameter and the data member regular ints, rather than pointers to int.

Summarizing:

struct node {         
  int data;         
  struct node* left; 
  struct node* right;
};                   

struct node *NewNode(int value) 
{
  struct node* new_key = malloc(sizeof *new_key);
  if ( new_key )
  {
    new_key->data = value;
    new_key->left = NULL;
    new_key->right = NULL;
  }
  return new_key;  
}                   

EDIT

If you want to create an array of nodes, do so in a function that calls NewNode, not in the NewNode function itself:

#define INITIAL_SIZE 1

struct node *CreateNodeArray( size_t *finalArraySize )
{
  *finalArraySize = 0;
  size_t i = 0;

  /**
   * For the purpose of this example, we'll start with an array of size
   * 1 and double it each time we hit the limit, but in practice you'd
   * want to start with a minimum size large enough to handle most
   * cases.
   */
  struct node *new_node = malloc( sizeof *new_node * INITIAL_SIZE );
  if ( new_node )
  {
    *finalArraySize = INITIAL_SIZE;

    while ( there_is_more_data() )
    {
      /**
       * First, check to see if we've hit the end of our array
       */
      if ( i == *finalArraySize )
      {
        /**
         * We've hit the end of the array, so we need to extend
         * it; in this case, we'll double its size
         */
        struct node *tmp = realloc( new_node, 
                                    sizeof *new_node * (*finalArraySize * 2) );              
        if ( tmp )
        {
          *finalArraySize *= 2;
          new_node = tmp;
        }
      }

      /**
       * Add a new node to the array
       */
      int data = getInput();
      new_node[i++] = NewNode( data ); 
    }
  }
  return new_node;
}

This code makes some assumptions about how you're building the individual nodes, but it should illustrate the point I'm trying to make, which is that you want cleanly separate building the array of nodes from building a single node.