JavaScript O(N) 131 124 116 92 (86?)

Golfed version:

function m(i,x){h={};n=[];for(a=2;a--;i=x)i.map(function(b){h[b]=h[b]||n.push(b)});return n}

Human readable golfed version:

function m(i,x) {
   h = {}
   n = []
   for (a = 2; a--; i=x)
      i.map(function(b){
        h[b] = h[b] || n.push(b)
      })
   return n
}

I could use concat like so and do it in 86 characters:

function m(i,x){h={};n=[];i.concat(x).map(function(b){h[b]=h[b]||n.push(b)});return n}

But I am not sure if it is still O(N) based on this JsPerf: http://jsperf.com/unique-array-merging-concat-vs-looping as the concat version is marginally faster with smaller arrays but slower with larger arrays (Chrome 31 OSX).

In practice do this (golf is full of bad practices):

function merge(a1, a2) {
   var hash = {};
   var arr = [];
   for (var i = 0; i < a1.length; i++) {
      if (hash[a1[i]] !== true) {
        hash[a1[i]] = true;
        arr[arr.length] = a1[i];
      }
   }
   for (var i = 0; i < a2.length; i++) {
      if (hash[a2[i]] !== true) {
        hash[a2[i]] = true;
        arr[arr.length] = a2[i];
      }
   }
   return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6]));

I'm not great at computing complexity but I believe this is O(N). Would love if someone could clarify.

Edit: Here is a version that takes any number of arrays and merges them.

function merge() {
   var args = arguments;
   var hash = {};
   var arr = [];
   for (var i = 0; i < args.length; i++) {
      for (var j = 0; j < args[i].length; j++) {
        if (hash[args[i][j]] !== true) {
          arr[arr.length] = args[i][j];
          hash[args[i][j]] = true;
        }
      }
    }
   return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7,8]));

Python 2.7, 38 chars

F=lambda x,y:{c:1 for c in x+y}.keys()

Should be O(N) assuming a good hash function.

Wasi's 8 character set implementation is better, if you don't think it violates the rules.

Array.prototype.unique = function()
{
  var o = {},i = this.length
  while(i--)o[this[i]]=true
  return Object.keys(o)
}

A function that would take n arrays could be the following:

function m()
{
  var o={},a=arguments,c=a.length,i;
  while(c--){i=a[c].length;while(i--)o[a[c][i]] = true} 
  return Object.keys(o);
}

Golfed, I think this should work ( 117 chars )

function m(){var o={},a=arguments,c=a.length,i;while(c--){i=a[c].length;while(i--)o[a[c][i]]=1}return Object.keys(o)}

Update If you want to keep the original type, you could

function m()
{
  var o={},a=arguments,c=a.length,f=[],g=[];
  while(c--)g.concat(a[c])
  c = g.length      
  while(c--){if(!o[g[c]]){o[g[c]]=1;f.push(g[c])}}
  return f
}

or golfed 149:

function m(){var o={},a=arguments,c=a.length,f=[],g=[];while(c--)g.concat(a[c]);c= g.length;while(c--){if(!o[g[c]]){o[g[c]]=1;f.push(g[c])}}return f}

This still can cast some doubts, if you want to distinguish 123 and '123', then this would not work..

python,46

def A(a,b):print[i for i in b if i not in a]+a

Or, using set operation simply

python, 8

set(a+b)

Perl

23 bytes, if we only count the code block inside subroutine. Could be 21, if overwriting global values is allowed (it would remove my from the code). It returns elements in random order, because order doesn't matter. As for complexity, on average it's O(N) (depends on number of hash collisions, but they are rather rare - in worst case it can be O(N²) (but this shouldn't happen, because Perl can detect pathological hashes, and changes the hash function seed when it detects such behavior)).

use 5.010;
sub unique{
    my%a=map{$_,1}@_;keys%a
}
my @a1 = (1, 2, 3, 4);
my @a2 = (3, 4, 5, 6);
say join " ", unique @a1, @a2;

Output (also showing randomness):

/tmp $ perl unique.pl 
2 3 4 6 1 5
/tmp $ perl unique.pl 
5 4 6 2 1 3

Fortran: 282 252 233 213

Golfed version:

function f(a,b,m,n) result(d);integer::m,n,a(m),b(n),c(m+n);integer,allocatable::d(:);j=m+1;c(1:m)=a(1:m);do i=1,n;if(.not.any(b(i)==c(1:m)))then;c(j)=b(i);j=j+1;endif;enddo;allocate(d(j-1));d=c(1:j-1);endfunction

Which not only looks infinitely better but will actually compile (too long a line in its golfed form) with the human-readable form:

function f(a,b,m,n) result(d)
  integer::m,n,a(m),b(n),c(m+n)
  integer,allocatable::d(:)
  j=m+1;c(1:m)=a(1:m)
  do i=1,n
     if(.not.any(b(i)==c(1:m)))then
        c(j)=b(i);j=j+1
     endif
  enddo
  allocate(d(j-1))
  d=c(1:j-1)
end function

This should be O(n) as I copy a into c and then check each b against all of c. The last step is to eliminate the garbage that c will contain since it is uninitialized.

One way in Ruby

To keep within the rules outlined above, I would use a similar strategy as the JavaScript solution and use a hash as an intermediary.

merged_arr = {}.tap { |hash| (arr1 + arr2).each { |el| hash[el] ||= el } }.keys

Essentially, these are the steps I'm going through in the line above.

1. Define a variable merged_arr that will contain the result
2. Initialize an empty, unnamed hash as an intermediary to put unique elements in
3. Use Object#tap to populate the hash (referenced as hash in the tap block) and return it for subsequent method chaining
4. Concatenate arr1 and arr2 into a single, unprocessed array
5. For each element el in the concatenated array, put the value el in hash[el] if no value of hash[el] currently exists. The memoization here (hash[el] ||= el) is what ensures the uniqueness of elements.
6. Fetch the keys (or values, as they are the same) for the now populated hash

This should run in O(n) time. Please let me know if I've made any inaccurate statements or if I can improve the above answer either for efficiency or readability.

Possible improvements

Using memoization is probably unnecessary given that the keys to the hash are going to be unique and the values are irrelevant, so this is sufficient:

merged_arr = {}.tap { |hash| (arr1 + arr2).each { |el| hash[el] = 1 } }.keys

I really love Object#tap, but we can accomplish the same result using Enumerable#reduce:

merged_arr = (arr1 + arr2).reduce({}) { |arr, val| arr[val] = 1; arr }.keys

You could even use Enumberable#map:

merged_arr = Hash[(arr1 + arr2).map { |val| [val, 1] }].keys

How I would do it in practice

Having said all that, if I were asked to merge two arrays arr1 and arr2 such that the result merged_arr has unique elements and could use any Ruby method at my disposal, I would simply use the set union operator which is intended for solving this exact problem:

merged_arr = arr1 | arr2

A quick peek at the source of Array#|, though, seems to confirm that using a hash as an intermediary seems to be the acceptable solution to performing a unique merge between 2 arrays.

Mathematica 10 Chars

Union[a,b]

Example:

a={1,2,3,4,5};
b={1,2,3,4,5,6};
Union[a,b]

{1, 2, 3, 4, 5, 6}

Mathematica2 43 Chars

Sort@Join[a, b] //. {a___, b_, b_, c___} :> {a, b, c}

PHP, 69/42 68/41 chars

Including the function declaration is 68 characters:

function m($a,$b){return array_keys(array_flip($a)+array_flip($b));}

Not including the function declaration is 41 characters:

array_keys(array_flip($a)+array_flip($b))

Javascript 86

Golfed version:

function m(a,b){var h={};return a.concat(b).filter(function(v){return h[v]?0:h[v]=1})}

Readable version:

function merge(a, b) {
  var hash = {};
  return a.concat(b).filter(function (val) {
    return hash[val] ? 0 : hash[val] = 1;
  });
}

JavaScript 60

I'm using ES6 generator.
The following is testable using Google's Traceur REPL.

m=(i,j)=>{h={};return[for(x of i.concat(j))if(!h[x])h[x]=x]}