How can I add new methods to Iterator?

In your particular case, it’s because you have implemented your trait for an iterator of String, but your vector is providing an iterator of &str. Here’s a more generic version:

use std::collections::HashSet;
use std::hash::Hash;

struct Unique<I>
where
    I: Iterator,
{
    seen: HashSet<I::Item>,
    underlying: I,
}

impl<I> Iterator for Unique<I>
where
    I: Iterator,
    I::Item: Hash + Eq + Clone,
{
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some(x) = self.underlying.next() {
            if !self.seen.contains(&x) {
                self.seen.insert(x.clone());
                return Some(x);
            }
        }
        None
    }
}

trait UniqueExt: Iterator {
    fn unique(self) -> Unique<Self>
    where
        Self::Item: Hash + Eq + Clone,
        Self: Sized,
    {
        Unique {
            seen: HashSet::new(),
            underlying: self,
        }
    }
}

impl<I: Iterator> UniqueExt for I {}

fn main() {
    let foo = vec!["a", "b", "a", "cc", "cc", "d"];

    for s in foo.iter().unique() {
        println!("{}", s);
    }
}

Broadly, we create a new extension trait called UniqueExt which has Iterator as a supertrait. When Iterator is a supertrait, we will have access to the associated type Iterator::Item.

This trait defines the unique method, which is only valid to call when then iterated item can be:

1. Hashed
2. Compared for total equality
3. Cloned

Additionally, it requires that the item implementing Iterator have a known size at compile time. This is done so that the iterator can be consumed by the Unique iterator adapter.

The other important part is the blanket implementation of the trait for any type that also implements Iterator:

impl<I: Iterator> UniqueExt for I {}