InvalidSelectorException using CSS selector to loc

Motivation

To utilize Selenium's CSS selector mechanism alongside with CSS attribute selectors and the HTML5 data- custom attribute to address specific hooks for elements.

Issue

While using the above to locate an element assigned with a CSS classname and the data- attribute, the following exception is thrown:

Caused by: org.openqa.selenium.remote.ErrorHandler$UnknownServerException: The given selector .gs-a-btn["data-value"] is either invalid or does not result in a WebElement. The following error occurred:
[Exception... "An invalid or illegal string was specified"  code: "12" nsresult: "0x8053000c (NS_ERROR_DOM_SYNTAX_ERR)"  location: "file:///C:/DOCUME~1/eliranm/LOCALS~1/Temp/anonymous6109849275533680625webdriver-profile/extensions/fxdriver@googlecode.com/components/driver_component.js Line: 5956"]
Build info: version: '2.23.1', revision: '17143', time: '2012-06-08 18:59:28'
System info: os.name: 'Windows XP', os.arch: 'x86', os.version: '5.1', java.version: '1.6.0_31'
Driver info: driver.version: unknown
    at <anonymous class>.<anonymous method>(file:///C:/DOCUME~1/eliranm/LOCALS~1/Temp/anonymous6109849275533680625webdriver-profile/extensions/fxdriver@googlecode.com/components/driver_component.js:6537)

Relevant Code

public void previous(String type) {
    By cssSelector = By.cssSelector(".gs-a-btn[data-value='" + type + "']");
    driver.findElement(cssSelector).click();
}

What have I tried

replacing single quotes with escaped double quotes inside the attribute selector query.
specifying attribute selector instead of attribute-value selector, i.e. ".gs-a-btn[\"data-value\"]" rather ".gs-a-btn[data-value='" + type + "']".
to look up information in references, such as the Selenium Reference, for any restrictions on CSS attribute selectors. the document specifically states that:

Currently the css selector locator supports all css1, css2 and css3 selectors except namespace in css3, some pseudo classes(:nth-of-type, :nth-last-of-type, :first-of-type, :last-of-type, :only-of-type, :visited, :hover, :active, :focus, :indeterminate) and pseudo elements(::first-line, ::first-letter, ::selection, ::before, ::after).

The reference you linked is for Selenium IDE.

Selenium WebDriver documentation can be found mainly on the official site here (basic usage) and here (advanced usage), but also here (a.k.a "What didn't make it into the docs yet" - especially the FAQ, Advanced User Interactions and lots of info about Selenium internals). The main source of information are, of course, the JavaDocs.

Anyway. The CSS Selectors supported by Selenium are those supported by the browser beneath it (with the exception of Selenium RC which has a Sizzle CSS engine), so your example should definitely work. Using this simple testpage:

<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="utf-8" />
    </head>
    <body>
        <input type="text" id="myInput" class="field" data-test="testytest" />
    </body>
</html>

I was able to sucessfully run this in both IE 8 (!!) and Firefox 13:

WebDriver driver = new FirefoxDriver();
driver.get("path to the file");
By cssSelector = By.cssSelector(".field[data-test='testytest']");
        // or By.cssSelector(".field[data-test=testytest]")
        // or By.cssSelector(".field[data-test]")
driver.findElement(cssSelector).sendKeys("Hello");
driver.quit();

So I digged more. If you try to run any of this in FF13 Firebug console:

document.querySelector(".field[data-test]")
document.querySelector(".field[data-test=testytest]")
document.querySelector(".field[data-test='testytest']")

it returns the right element. However, any of this:

document.querySelector(".field['data-test']")
document.querySelector(".field[\"data-test\"]")

fails with "An invalid or illegal string was specified" error (both in Firefox and IE) which is correct (and, therefore, the error message you got was right, the selector is invalid).

Please, try once more, get rid of any quotes, make sure your type variable doesn't contain any quotes or backslashes or whatnot. The construct should definitely work. If it doesn't, post the new exception stack trace so we can see the exact selector that caused it.