Language INtegrated Query ou consulta integrada à linguagem é uma tecnologia, e por isso pode ser considerado um mecanismo para facilitar consultas a dados organizados em coleções.

LINQ To SQL

O principal intuito da sua criação foi ter uma linguagem declarativa disponível para o .NET e de certa forma substituir o SQL. Assim você pode escrever a query para o banco de dados em C# (pode ser outra linguagem desde que o compilador dela ajude) sem estar vinculado a nenhum banco de dados. A consulta é transformada em uma string SQL para o banco de dados que estiver sendo consultado. A consulta é feita através de um repositório, geralmente fornecido pelo Entity Framework, mas pode ser qualquer outra forma que se conforme com os protocolos do LINQ.

Tanto é assim que a sintaxe é muito parecida com SQL. Algumas pessoas até criticam os nomes dos métodos porque não seguem o padrão mais funcional de fazer isso, mas o objetivo era ser próximo do SQL.

Um banco de dados pode ser acessado por LINQ desde que ele forneça um tradutor do LINQ para o seu SQL. São os LINQ Providers (uma lista de alguns existentes).

Na verdade LINQ é tão poderoso que pode consultar bancos que não usam SQL, ou mesmo que não sejam relacionais. Para o LINQ funcionar só precisa ter uma coleção de dados.

LINQ To XXX

Não precisa nem ser banco de dados. Pode fazer em arquivos diversos, seja um texto simples, ou um formato específico, XML, JSON, um código fonte de uma linguagem, um DataSet de uma conexão ADO.NET etc., além de acessos a dispositivos externos (rede em vários protocolos, sockets, etc.). Enfim, onde tenha um stream de dados pode usar o LINQ. Novamente, desde que alguém forneça um conjunto de classes que permita acessar esses dados de forma apropriada.

Essas casos mais simples que não possui uma linguagem de consulta, como é o caso do SQL, é bem mais fácil porque ele não tem que avaliar toda expressão e criar um texto para enviar ao banco de dados ou outro mecanismo de acesso à dados. Basta ter um mecanismo que vá lendo as informações em algum lugar e entregando uma a uma para o LINQ, conforme solicitado.

LINQ To Objects

Obviamente que coleções em memória podem ser usadas também. Então um List, Dictionary, array, etc. podem ser usados.

Há casos que é tão simples fornecer os dados que não precisa fornecer algo adicional para acessá-los. Vamos dizer que você faça uma coleção nova para usar, sei lá, um AVLTree, basta que esta coleção seja enumerável que o LINQ já funciona com ela, a biblioteca padrão fornece os mecanismos necessários.

Como funciona

O LINQ é um conjunto de métodos de extensão que manipulam algo que seja IEnumerable (coleções normais) ou IQueryable (coleções que precisam ser traduzidas). Esses métodos vão manipulando item por item da coleção (em vários casos através de yield) e podem ser compostos entre si.

Esses métodos podem ser usados de forma imperativa ou declarativa (depende do compilador). Na forma imperativa usa a tal da fluent interface. Na declarativa uma forma evoluída que elimina o "ruído" e integra melhor com a linguagem hospedeira (C#, por exemplo).

Para instruir o que fazer o LINQ usa muito lambdas (funcionamento).

Então podemos estender o uso do LINQ de duas formas:

• podemos criar novos fornecedores de dados para o LINQ processar e
• podemos criar novos métodos de consultas específicas para serem aplicados no LINQ, ainda que eles não possam ser utilizados na forma declarativa.

Veja o fonte do Any() em coleções simples (.NET Core). E o fonte do Any() para fontes de dados externas (até onde eu sei é para SQL Server).

O LINQ impõe um overhead de execução em coleções, principalmente em memória. Então deve-se pensar se vale a pena seu uso. Na maioria das vezes vale, mas tem que saber usar.

Com o PLINQ cria-se uma abstração que facilita o uso da varredura paralela nas coleções.

Pode ver Como funciona a lógica do Where no Entity Framework?. Os demais métodos funcionam do mesmo jeito.

Mais informações

Pode ver exemplos que a Microsoft fornece. Os links desta resposta estão cheios de exemplos. Exemplos práticos reais em toda linq.

A maioria das linguagens podem ter algo semelhante mesmo sem ajuda do compilador (só a forma imperativa), basta ter uma forma geral de tratar coleções e geradores de elementos (yield). Só para dar um exemplo fizeram para TypeScript.

Leia também: Para que serve o System.Linq no C#? (será dup?)

Aconselho ver a documentação oficial.

É o que dá para responder aqui, cabem perguntas mais específicas.

Consulta integrada à linguagem (LINQ) é que uma inovação introduzido no .NET Framework versão 3.5 que as pontes a lacuna entre o mundo de objetos e o mundo dos dados.

Tradicionalmente, consultas em dados são expressos como cadeias de caracteres simples sem verificação de tipo em compilar tempo ou suporte a IntelliSense. Além disso, você terá de aprender uma linguagem de consulta diferente para cada tipo de fonte de dados: SQL bancos de dados, documentos XML, vários serviços da Web e assim por diante. LINQ faz um consulta uma construção de linguagem de primeira classe em c#. Você escrever consultas em relação a coleções com rigidez de tipos de objetos usando palavras-chave e operadores familiares.

Veja neste link https://msdn.microsoft.com/pt-br/library/mt693042.aspx