Solution first
Make productOptions an Object instead of an Array and use jQuery.extend() to merge the productOptions with the rest of the data to be used in the ajax request.
var productOptions = new Object();
productOptions['color']="test1";
productOptions['size']="test2";
$.ajax({
  type: "GET",
  url: "test.js",
  dataType: "script",
  data: jQuery.extend({action: 'add'}, productOptions)
});
Yields GET test.js?_=randomjQueryNumber&action=add&color=test1&size=test2
The lengthy explanation
Your problem mainly originates from the error you made assuming the Array object is the same as an associative array. An array has only a number of entries which are accessed by a zero-based index. While an associative array consists of (key, value) pairs.
There is a simple test you can make
Variant 1
var productOptions=new Array();
productOptions[0]="test1";
productOptions[1]="test2";
alert(productOptions.length); //yields 2
Note: If e.g. you replace productOptions[0] with productOptions[4] the alert will display 5!!
Variant 2
var productOptions=new Array();
productOptions['color']="test1";
productOptions['size]="test2";
alert(productOptions.length); //yields 0
Variant 1 productOptions[0]="test1"; behaves similar to productOptions.push("test1"); (but isn't the same - check the Note under Variant 1 - push appends to the end of the array and the other syntax just sets the element at the specified index).
Variant 2 productOptions['color']="test1"; doesn't even work on the "array"; This syntax does the same as it does with every javascript object, it sets the property color to the value test1 on the object.
So if you use the syntax from the second variant you actually created an empty javascript array object with two properties color and size. Easy test
alert(productOptions.color); //yields test1
alert(productOptions.size); //yields test2
alert(productOptions[0]); //yields undefined
That's why the variant 1 works. There productOptions is a valid array and jQuery converts it to a query string which looks like this option=test1&option=test2.
The second variant is also handled correctly by jQuery as option:productOptions actually is the same as option:new Array();